<题目链接>
题目大意:
给定一个$[1,n]$的区间($1\leq10^5$),区间内每个位置的颜色都是它的区间下标。
现在进行两种操作:
1.将区间$[l,r]$全部染成$x$颜色,并且对区间值的贡献为|x-c| (c为原来区间的颜色)
2.查询区间贡献之和
解题分析:
多增加一个变量用于判断区间颜色是否相同,更新到区间颜色相同的部分时,就进行lazy,同时lazy维护一下多出来的贡献。
#include <bits/stdc++.h> using namespace std; #define Lson rt<<1,l,mid #define Rson rt<<1|1,mid+1,r #define REP(i,s,t) for(int i=s;i<=t;i++) const int N = 1e5+5; int n,m,cnt; typedef long long ll; template<typename T> inline void read(T&x){ x=0;int f=1;char ch=getchar(); while(ch<'0' ||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } x*=f; } struct Seg{ ll val,col,add; #define val(rt) tr[rt].val #define col(rt) tr[rt].col #define add(rt) tr[rt].add }tr[N<<2]; inline void Pushdown(int rt,int len){ if(add(rt)){ add(rt<<1)+=add(rt); add(rt<<1|1)+=add(rt); val(rt<<1)+=(len-(len>>1))*add(rt); val(rt<<1|1)+=(len>>1)*add(rt); col(rt<<1)=col(rt<<1|1)=col(rt); add(rt)=0; } } inline void Pushup(int rt){ val(rt)=val(rt<<1)+val(rt<<1|1); if(col(rt<<1)==col(rt<<1|1))col(rt)=col(rt<<1|1); else col(rt)=0; } void build(int rt,int l,int r){ if(l==r){ col(rt)=l; return; } int mid=l+r>>1; build(Lson);build(Rson); Pushup(rt); } void update(int rt,int l,int r,int L,int R,int c){ if(L<=l && r<=R && col(rt)){ val(rt)+=(r-l+1)*(abs(c-col(rt))); add(rt)+=abs(c-col(rt)); col(rt)=c; return; } Pushdown(rt,r-l+1); int mid=l+r>>1; if(L<=mid)update(Lson,L,R,c); if(R>mid)update(Rson,L,R,c); Pushup(rt); } ll query(int rt,int l,int r,int L,int R){ if(L<=l && r<=R)return val(rt); Pushdown(rt,r-l+1); int mid=l+r>>1; ll ans=0; if(L<=mid)ans+=query(Lson,L,R); if(R>mid)ans+=query(Rson,L,R); return ans; } int main(){ read(n);read(m); build(1,1,n); while(m--){ int op;read(op); if(op==1){ int u,v;ll w;read(u);read(v);read(w); update(1,1,n,u,v,w); }else{ int u,v;read(u);read(v); printf("%lld\n",query(1,1,n,u,v)); } } }