【*2200线段树Pushup】CF1567 E

冷不防 2024-03-17 17:54 41阅读 0赞

[Problem - E - Codeforces][]

题意：

![b7beb74d49e74c8897a1e2cd5f65c1f3.png][]

思路：

维护这些信息即可

![63536a4623814a7f85e792790a048c25.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    struct info{
    	int mx,lmx,rmx,sz,cnt=0;
    	int lval,rval;
    };
    
    info operator+(const info &l,const info &r){
    	info res;
    
    	res.cnt=l.cnt+r.cnt;
    	if(l.rval<=r.lval) res.cnt+=l.rmx*r.lmx;
    
    	res.sz=l.sz+r.sz;
    	res.lval=l.lval;
    	res.rval=r.rval;
    
    	if(l.mx==l.sz){
    		if(l.rval<=r.lval) res.lmx=l.sz+r.lmx;
    		else res.lmx=l.sz;
    	}else{
    		res.lmx=l.lmx;
    	}
    
    	if(r.mx==r.sz){
    		if(l.rval<=r.lval) res.rmx=r.sz+l.rmx;
    		else res.rmx=r.sz;
    	}else{
    		res.rmx=r.rmx;
    	}
    
    	res.mx=max(l.mx,r.mx);
    
    	if(l.rval<=r.lval) res.mx=max(res.mx,l.rmx+r.lmx);
    
    	return res;
    }
    
    struct Segtree{
    	info Val;
    }tree[mxe<<2];
    
    int N,Q,op,x,y,l,r;
    int a[mxn];
    
    void pushup(int rt){
    	tree[rt].Val=tree[rt<<1].Val+tree[rt<<1|1].Val;
    }
    void build(int rt,int l,int r){
    	if(l==r){
    		tree[rt].Val.cnt=1;
    		tree[rt].Val.lmx=tree[rt].Val.rmx=tree[rt].Val.mx=tree[rt].Val.sz=1;
    		tree[rt].Val.lval=tree[rt].Val.rval=a[l];
    		return;
    	}
    	int mid=l+r>>1;
    	build(rt<<1,l,mid);
    	build(rt<<1|1,mid+1,r);
    	pushup(rt);
    }
    void change(int rt,int l,int r,int x,int k){
    	if(l==r){
    		tree[rt].Val.cnt=1;
    		tree[rt].Val.lmx=tree[rt].Val.rmx=tree[rt].Val.mx=tree[rt].Val.sz=1;
    		tree[rt].Val.lval=tree[rt].Val.rval=k;
    		return;
    	}
    	int mid=l+r>>1;
    	if(x<=mid) change(rt<<1,l,mid,x,k);
    	else change(rt<<1|1,mid+1,r,x,k);
    	pushup(rt);
    }
    info query(int rt,int l,int r,int x,int y){
    	if(x<=l&&r<=y){
    		return tree[rt].Val;
    	}
    	int mid=l+r>>1;
    	if(x>mid) return query(rt<<1|1,mid+1,r,x,y);
    	else if(y<=mid) return query(rt<<1,l,mid,x,y);
    	else{
    		return query(rt<<1,l,mid,x,y)+query(rt<<1|1,mid+1,r,x,y);
    	}
    }
    void solve(){
    	cin>>N>>Q;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	build(1,1,N);
    	while(Q--){
    		cin>>op;
    		if(op==1){
    			cin>>x>>y;
    			change(1,1,N,x,y);
    		}else{
    			cin>>l>>r;
    			cout<<query(1,1,N,l,r).cnt<<'\n';
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/1567/problem/E
[b7beb74d49e74c8897a1e2cd5f65c1f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b2bd1e399c7942f8a9d6ee31291537f2.png
[63536a4623814a7f85e792790a048c25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/edcda07bc2df410cb13ef5208d6e77a5.png