正題

題目鏈接:https://www.luogu.com.cn/problem/CF444C

---

題目大意

$n$個物品第$i$個顏色為$i$，權值為$0$。要求支持$m$次操作

給出$l,r,x$，對于所有區間$[l,r]$中的物品，如果顏色為$c$，那么該位置的權值加上$|c?x|$，并且顏色改為$x$

詢問區間權值和

---

解題思路

區間染色有一種簡單的做法并且可以求出每個被染色的相同顏色段。

用$set$維護每個相同的連續顏色段，那么每次修改最多會產生$3$個新的顏色端。均攤下來就是$O(n\log n)$了。

然后加一個線段樹維護權值就好了，總時間復雜度也是$O(n\log n)$的

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<set> #define ll long long #define lowbit(x) (x&-x) using namespace std; const ll N=1e5+10; struct node{ll l,r,w;node(ll L=0,ll rr=0,ll ww=0){l=L;r=rr;w=ww;return;} }; multiset<node> s; ll n,m; bool operator<(node x,node y) {return x.r<y.r;} struct TreeBinary{ll w[N<<2],lazy[N<<2];void Downdata(ll x,ll l,ll r){if(!lazy[x])return;ll mid=(l+r)>>1;w[x*2]+=lazy[x]*(mid-l+1);w[x*2+1]+=lazy[x]*(r-mid);lazy[x*2]+=lazy[x];lazy[x*2+1]+=lazy[x];lazy[x]=0;return;}void Change(ll l,ll r,ll val,ll L=1,ll R=n,ll x=1){if(L==l&&R==r){w[x]+=val*(r-l+1);lazy[x]+=val;return;}ll mid=(L+R)>>1;Downdata(x,L,R); if(r<=mid)Change(l,r,val,L,mid,x*2);else if(l>mid)Change(l,r,val,mid+1,R,x*2+1);else Change(l,mid,val,L,mid,x*2),Change(mid+1,r,val,mid+1,R,x*2+1);w[x]=w[x*2]+w[x*2+1];return;}ll Ask(ll l,ll r,ll L=1,ll R=n,ll x=1){if(L==l&&R==r)return w[x];ll mid=(L+R)>>1;Downdata(x,L,R);if(r<=mid)return Ask(l,r,L,mid,x*2);if(l>mid)return Ask(l,r,mid+1,R,x*2+1);return Ask(l,mid,L,mid,x*2)+Ask(mid+1,r,mid+1,R,x*2+1); } }T; signed main() {multiset<node>::iterator it;scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)s.insert(node(i,i,i));while(m--){ll op,l,r,x;scanf("%lld%lld%lld",&op,&l,&r);if(op==1){scanf("%lld",&x); while(1){it=s.lower_bound(node(l,l,l));node tmp=*it;s.erase(it);if(tmp.l<l&&tmp.r>r)T.Change(l,r,abs(x-tmp.w));if(tmp.l<l){s.insert(node(tmp.l,l-1,tmp.w));if(tmp.r<=r)T.Change(l,tmp.r,abs(x-tmp.w));}if(tmp.r>r){s.insert(node(r+1,tmp.r,tmp.w));if(tmp.l>=l)T.Change(tmp.l,r,abs(x-tmp.w));break;}if(tmp.l>=l&&tmp.r<=r)T.Change(tmp.l,tmp.r,abs(x-tmp.w));if(tmp.r==r)break;}s.insert(node(l,r,x));}else printf("%lld\n",T.Ask(l,r));}return 0; }

總結

以上是生活随笔為你收集整理的CF444C-DZY Loves Colors【线段树,set】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。