【*2400 线段树】CF444 C

冷不防 2024-03-17 17:58 59阅读 0赞

[Problem - C - Codeforces][]

题意：

![format_png][]

思路：

首先询问的是权值和，那么维护一个区间和sum，因此pushup部分就好了

考虑修改，区间修改，因此要打标记

一次修改对区间和的贡献不能直接计算，因此我们考虑分开计算贡献，把这个区间分成几个由一种颜色构成的区间，对这些区间去产生贡献

如果一个区间的左右子区间颜色不一样，那么就继续递归下去算贡献

lazy标记的含义是，给这整个区间的颜色赋值为y，那么对区间和的贡献就是abs(x-y)，x为原来的颜色

**在设计lazy标记的含义时，考虑区间修改对val的贡献**

然后我们去考虑如何pushdown

在pushdown时，先去更新左右子区间的标记，然后去更新左右子区间的val，最后清空该区间的tag

在计算左右子区间的val时，记得用整个区间的tag去计算，为什么呢

在pushdown时，tag永远是为了子区间服务的，在计算本区间的val时不能用本区间的tag

那么对于这道题的pushdown：

更新标记：直接累加即可

更新val：和区间和同理

清空tag：lazy=0

区间修改和查询的代码就不详细解释了，都是一样的

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    const int mod=1e9+7;
    const int Inf=1e18;
    
    struct tag{
    	int laz=0;
    };
    
    struct info{
    	int sum=0,col=0,same=0,sz=0;
    	tag t;
    };
    
    info operator+(const info &l,const info &r){
    	info res;
    
    	res.sz=l.sz+r.sz;
    
    	res.sum=l.sum+r.sum;
    
    	res.col=0;
    	res.same=0;
    
    	if(l.same==1&&r.same==1&&l.col==r.col){
    		res.same=1;
    		res.col=l.col;
    	}
    
    	return res;
    }
    
    struct Segtree{
    	info Val;
    }tree[mxe<<2];
    
    int N,M,op,l,r,x;
    int col[mxn],a[mxn];
    
    void pushup(int rt){
    	tree[rt].Val=tree[rt<<1].Val+tree[rt<<1|1].Val;
    }
    void pushdown(int rt){
    	if(tree[rt].Val.t.laz!=0){
    		//左区间
    		tree[rt<<1].Val.t.laz+=tree[rt].Val.t.laz;
    		tree[rt<<1].Val.col=tree[rt].Val.col;
    		tree[rt<<1].Val.sum+=tree[rt<<1].Val.sz*tree[rt].Val.t.laz;
    
    		//右区间
    		tree[rt<<1|1].Val.t.laz+=tree[rt].Val.t.laz;
    		tree[rt<<1|1].Val.col=tree[rt].Val.col;
    		tree[rt<<1|1].Val.sum+=tree[rt<<1|1].Val.sz*tree[rt].Val.t.laz;
    
    		//清空tag
    		tree[rt].Val.t.laz=0;	
    	}
    }
    void build(int rt,int l,int r){
    	tree[rt].Val.t.laz=0;
    	if(l==r){
    		tree[rt].Val.sz=1;
    		tree[rt].Val.col=col[l];
    		tree[rt].Val.same=1;
    		tree[rt].Val.sum=0;
    		return;
    	}
    	int mid=l+r>>1;
    	build(rt<<1,l,mid);
    	build(rt<<1|1,mid+1,r);
    	pushup(rt);
    }
    info query(int rt,int l,int r,int x,int y){
    	if(x<=l&&r<=y){
    		return tree[rt].Val;
    	}
    	pushdown(rt);
    	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 modify(int rt,int l,int r,int x,int y,int k){
    	if(x<=l&&r<=y){
    		if(tree[rt].Val.same==1){
    			int p=tree[rt].Val.col;
    			tree[rt].Val.t.laz+=abs(p-k);
    			tree[rt].Val.col=k;
    			tree[rt].Val.sum+=abs(p-k)*tree[rt].Val.sz;
    			return;
    		}
    	}
    	pushdown(rt);
    	int mid=l+r>>1;
    	if(x<=mid) modify(rt<<1,l,mid,x,y,k);
    	if(y>mid) modify(rt<<1|1,mid+1,r,x,y,k);
    	pushup(rt);
    }
    void solve(){
    	cin>>N>>M;
    	for(int i=1;i<=N;i++) col[i]=i;
    	build(1,1,N);
    	for(int i=1;i<=M;i++){
    		cin>>op;
    		if(op==1){
    			cin>>l>>r>>x;
    			modify(1,1,N,l,r,x);
    		}else{
    			cin>>l>>r;
    			cout<<query(1,1,N,l,r).sum<<'\n';
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/444/problem/C
[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b337bd6055294162a1d97a97f1aae9d2.png