文章目錄

• 題意：
• 思路：

傳送門

題意：

給你一個數組$a$，初始價值全為$0$，顏色全為$1$，讓后讓你實現以下三個操作：

將$[l,r]$區間內的顏色都染成$c$。

將所有顏色為$c$的位置價值都加上$x$。

詢問$i$位置的價值。

$1\le n,q\le 1e6$

思路：

首先分析一下第二個操作是全局的，這就提示我們每次執行第二個操作的時候可以打一個懶標記$lazy[c]+=x$，當詢問某個點的價值的時候只需要輸出$a_i+lazy[c]$即可，$c$為當前點的顏色。

但是這都是不考慮第一個操作的情況下的，考慮第一個操作，假設$l==r$，我們將他分為兩個步驟：

首先將當前位置原本的顏色$c^{\prime }$對應的$lazy[c^{\prime }]$加到$a_l$上。

將當前顏色改成$c$。

上述步驟很明顯有一個問題，就是將修改前的$lazy[c]$的代價在第三個操作的時候也算進去了，這顯然是不對的，不過我們發現可以在第二部中將$a_l?lazy[c]$，這樣就可以消除上述多余的價值了。

我們解決了單個的，再來看區間的怎么搞。

直接暴力不可以，但是我們不難發現可以將其拆分成若干個區間，每個區間的顏色都相同，類似與珂朵莉樹，保證都是推平操作的話區間個數下降的很快的，這樣我們只需要用$set$維護這些區間，讓后快速找到并且可以遍歷這些區間修改他們，讓后將他們推平，這看似暴力的算法實際平攤下來是$O(q)$的，由于對于每個區間我們還需要實現區間加某個數，顯然$BIT$就可以實現，總復雜度是$O(qlogn)$。

#include<bits/stdc++.h> #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back #define IT set<node>::iterator #define x first #define y second using namespace std;const int N=2000010,INF=0x3f3f3f3f,mod=1e9+7; typedef long long LL; typedef pair<LL,LL> PII;int n,m; LL a[N]; vector<PII>v[N];struct node {int l,r,t;mutable int v;bool operator < (const node& o) const {return l<o.l;} }; set<node>s;int find(int col,int t) {int l=0,r=(int)v[col].size()-1,ans=-1;if(r==-1) return INF;while(l<=r) {int mid=l+r>>1;if(v[col][mid].y<t) ans=mid,l=mid+1;else r=mid-1;}return ans; }struct BIT {LL tr[N];#define lowbit(x) (x&(-x))void add(int x,LL c) {for(int i=x;i<N;i+=lowbit(i)) tr[i]+=c;}LL sum(int x) {LL ans=0;for(int i=x;i;i-=lowbit(i)) ans+=tr[i];return ans;} }bit;IT splitl(int pos) {IT it=s.upper_bound({pos,-1,-1,-1});--it;return it; }IT splitr(int pos) {IT it=s.upper_bound({pos,-1,-1,-1});return it; }void add(int l,int r,int c,int t) {IT itr=splitr(r+1);IT itl=splitl(l);for(;itl!=itr;++itl) {int ls=itl->l,rs=itl->r;ls=max(ls,l);rs=min(rs,r);int col=itl->v,t=itl->t;int pos=find(col,t);if(pos!=INF) {LL ed=v[col].back().x;if(pos!=-1) ed-=v[col][pos].x;bit.add(rs+1,-ed); bit.add(ls,ed);}}itl=splitl(l);node ls,rs;ls.l=-1; rs.l=-1;if(itl->l<l) {ls.l=itl->l; ls.r=l-1;ls.v=itl->v; ls.t=itl->t;}if(itl->r>r) {rs.l=r+1; rs.r=itl->r;rs.v=itl->v; rs.t=itl->t;}itr--;if(itr->r>r) {rs.l=r+1; rs.r=itr->r;rs.v=itr->v; rs.t=itr->t;}itr++;s.erase(itl,itr);if(ls.l!=-1) s.insert(ls);if(rs.l!=-1) s.insert(rs);s.insert({l,r,t,c}); }LL query(int pos) {IT now=splitl(pos);int t=now->t,col=now->v;pos=find(col,t);LL ans=0;if(pos!=INF) {LL ed=v[col].back().x;if(pos!=-1) ed-=v[col][pos].x;ans+=ed;}return ans; }void solve() {scanf("%d%d",&n,&m);s.insert({1,n,0,1});for(int i=1;i<=m;i++) {char ss[10];scanf("%s",ss+1);if(ss[1]=='C') {int l,r,c; scanf("%d%d%d",&l,&r,&c);add(l,r,c,i);} else if(ss[1]=='A') {int c,x; scanf("%d%d",&c,&x);if(v[c].size()) {LL ed=v[c].back().x;v[c].pb({x+ed,i});}else v[c].pb({x,i});} else if(ss[1]=='Q') {int x; scanf("%d",&x);printf("%lld\n",bit.sum(x)+query(x));}} }int main() {int _=1;while(_--) {solve();}return 0; }

總結

以上是生活随笔為你收集整理的CF 1638 E. Colorful Operations set 区间平推的全部內容，希望文章能夠幫你解決所遇到的問題。

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