这题我写了四种做法……
思路
不管做法怎样，思路都是一样的。
好吧，其实不一样，有细微的差别。
第一种
考虑位置$x$对区间$[l,r]$有$\pm x$的贡献当且仅当$pre_x!!<!l ;or;nxt\_x!!>!r$，其中$pre,nxt$表示与$x$同种颜色的前驱后继。
那么题目就转化为二维数点了：一维是位置，一维是前驱/后继，权值是$\pm$位置。
第二种
考虑最后的减去开始的等价于每一位减去前面的。
即位置$x$的贡献是$x-pre_x,pre_x\geq l$。
那么题目同样转化为二维数点：一维是位置，一维是前驱，权值是$x-pre_x$。
做法
做法一
按照第一种思路，暴力树套树。
然而这样你会发现自己要么MLE要么RE……
做法二
按照第一种思路，莫队+树状数组。
然而你会不停地TLE，而且我的卡常技巧不够高超，放弃了。
做法三
按照第二种思路，莫队+树状数组。
并不需要怎么卡常就可以过。
做法四
这个是正解了。CDQ分治+二维数点。
用第二种思路，每次$pre_x$的变动可以变为在$(x,pre_x)$这个点上加减$x-pre_x$，询问可以变为查询以$(l,l)$为左下角，$(r,n)$为右上角的矩形之和。按照时间CDQ分治，每次算左边的点对右边的矩形的贡献。
然而这个矩形不好看，似乎还要差分/树套树？
其实并不用。考虑$x>pre_x$，所以直线$y=x$上方是没有点的，可以把查询变成以$(1,l)$为左下角，$(r,n)$为右上角的矩形。这样可以扫描线+树状数组了。
时间复杂度应该是$O(n\log^2 n)$。
代码
做法一
1#include<bits/stdc++.h> 2namespace my_std{ 3 using namespace std; 4 #define pii pair<int,int> 5 #define fir first 6 #define sec second 7 #define MP make_pair 8 #define rep(i,x,y) for (int i=(x);i<=(y);i++) 9 #define drep(i,x,y) for (int i=(x);i>=(y);i--) 10 #define go(x) for (int i=head[x];i;i=edge[i].nxt) 11 #define sz 101010 12 typedef long long ll; 13 template<typename T> 14 inline void read(T& t) 15 { 16 t=0;char f=0,ch=getchar(); 17 double d=0.1; 18 while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar(); 19 while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar(); 20 if(ch=='.') 21 { 22 ch=getchar(); 23 while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar(); 24 } 25 t=(f?-t:t); 26 } 27 template<typename T,typename... Args> 28 inline void read(T& t,Args&... args){read(t); read(args...);} 29 void file() 30 { 31 #ifndef ONLINE_JUDGE 32 freopen("a.txt","r",stdin); 33 #endif 34 } 35// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;} 36} 37using namespace my_std; 38 39int n,m; 40int a[sz]; 41int pre[sz],nxt[sz]; 42set<int>s[sz]; 43 44#define Tree sz*100 45int Ls[Tree],Rs[Tree]; 46ll sum[2][Tree]; // 0:pre 1:nxt 47#define Lson Ls[k],l,mid 48#define Rson Rs[k],mid+1,r 49int cnt; 50int bin[Tree],top; 51void del(int &k){Ls[k]=Rs[k]=sum[0][k]=sum[1][k]=0;bin[++top]=k;k=0;} 52int newnode(){return top?bin[top--]:++cnt;} 53void Add(int &k,int l,int r,int x,int y,int t) 54{ 55 if (!k) k=newnode(); 56 sum[t][k]+=y; 57 if (l==r) { if (!sum[0][k]&&!sum[1][k]) del(k); return; } 58 int mid=(l+r)>>1; 59 if (x<=mid) Add(Lson,x,y,t); 60 else Add(Rson,x,y,t); 61 if (!sum[0][k]&&!sum[1][k]) del(k); 62} 63ll Query(int k,int l,int r,int x,int y,int t) 64{ 65 if (!k||x>y||!sum[t][k]) return 0; 66 if (x<=l&&r<=y) return sum[t][k]; 67 int mid=(l+r)>>1;ll ret=0; 68 if (x<=mid) ret+=Query(Lson,x,y,t); 69 if (y>mid) ret+=Query(Rson,x,y,t); 70 return ret; 71} 72void Debug(int k,int l,int r,int t) 73{ 74 if (!k) { rep(i,l,r) printf("0 "); return; } 75 if (l==r) return (void)printf("%lld ",sum[t][k]); 76 int mid=(l+r)>>1; 77 rep(i,0,1) assert(sum[i][k]==sum[i][Ls[k]]+sum[i][Rs[k]]); 78 Debug(Lson,t);Debug(Rson,t); 79} 80#undef Lson 81#undef Rson 82 83int root[sz<<2]; 84#define ls k<<1 85#define rs k<<1|1 86#define lson ls,l,mid 87#define rson rs,mid+1,r 88ll query(int k,int l,int r,int x,int y) 89{ 90 if (x<=l&&r<=y) 91 { 92 ll a=Query(root[k],0,n+1,y+1,n+1,1),b=Query(root[k],0,n+1,0,x-1,0); 93 return a-b; 94 } 95 int mid=(l+r)>>1;ll ret=0; 96 if (x<=mid) ret+=query(lson,x,y); 97 if (y>mid) ret+=query(rson,x,y); 98 return ret; 99} 100void debug(int k,int l,int r) 101{ 102 printf("%d ~ %d:\n",l,r); 103 printf("pre: ");Debug(root[k],0,n+1,0);puts(""); 104 printf("nxt: ");Debug(root[k],0,n+1,1);puts(""); 105 if (l==r) return; 106 int mid=(l+r)>>1; 107 debug(lson);debug(rson); 108} 109void change(int k,int l,int r,int x,int a,int b) // pre[x]->a , nxt[x]->b 110{ 111 if (pre[x]!=-1) Add(root[k],0,n+1,pre[x],-x,0); 112 Add(root[k],0,n+1,a,x,0); 113 if (nxt[x]!=-1) Add(root[k],0,n+1,nxt[x],-x,1); 114 Add(root[k],0,n+1,b,x,1); 115 if (l==r) return; 116 int mid=(l+r)>>1; 117 if (x<=mid) change(lson,x,a,b); 118 else change(rson,x,a,b); 119} 120 121int calcPre(int x,int col){set<int>::iterator it=s[col].lower_bound(x);--it;return *it;} 122int calcNxt(int x,int col){return *(s[col].upper_bound(x));} 123 124int main() 125{ 126 file(); 127 int x,y,z; 128 read(n,m); 129 rep(i,1,n) s[i].insert(0),s[i].insert(n+1); 130 rep(i,1,n) read(a[i]),s[a[i]].insert(i); 131 rep(i,1,n) 132 { 133 int Pre=calcPre(i,a[i]),Nxt=calcNxt(i,a[i]); 134 pre[i]=nxt[i]=-1; 135 change(1,1,n,i,Pre,Nxt); 136 pre[i]=Pre,nxt[i]=Nxt; 137 } 138 while (m--) 139 { 140 read(z,x,y); 141 if (z==1) 142 { 143 if (y==a[x]) continue; 144 int Pre=calcPre(x,y),Nxt=calcNxt(x,y); 145 change(1,1,n,x,Pre,Nxt); 146 if (pre[x]!=0) change(1,1,n,pre[x],pre[pre[x]],nxt[x]); 147 if (nxt[x]!=n+1) change(1,1,n,nxt[x],pre[x],nxt[nxt[x]]); 148 if (Pre!=0) change(1,1,n,Pre,pre[Pre],x); 149 if (Nxt!=n+1) change(1,1,n,Nxt,x,nxt[Nxt]); 150 s[a[x]].erase(x);s[y].insert(x); 151 a[x]=y; 152 if (nxt[x]!=n+1) pre[nxt[x]]=pre[x]; 153 if (pre[x]!=0) nxt[pre[x]]=nxt[x]; 154 if (Pre!=0) nxt[Pre]=x; 155 if (Nxt!=n+1) pre[Nxt]=x; 156 pre[x]=Pre;nxt[x]=Nxt; 157 } 158 else printf("%lld\n",query(1,1,n,x,y)); 159 } 160}
做法二
代码被我瞎卡一波常数之后变得巨丑无比。
1#include<bits/stdc++.h> 2namespace my_std{ 3 using namespace std; 4 #define rep(i,x,y) for (R int i=x;i<=y;++i) 5 #define sz 101001 6 typedef long long ll; 7 template<typename T> 8 inline void read(T& t) 9 { 10 t=0;char f=0,ch=getchar(); 11 double d=0.1; 12 while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar(); 13 while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar(); 14 if(ch=='.') 15 { 16 ch=getchar(); 17 while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar(); 18 } 19 t=(f?-t:t); 20 } 21 template<typename T,typename... Args> 22 inline void read(T& t,Args&... args){read(t); read(args...);} 23 void file() 24 { 25 #ifndef ONLINE_JUDGE 26 freopen("a.txt","r",stdin); 27 #endif 28 } 29// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;} 30} 31using namespace my_std; 32 33int n,m; 34int a[sz]; 35int pre[sz],nxt[sz]; 36int w[2][sz]; // 0:pre 1:nxt 37set<int>s[sz]; 38 39ll S1; 40ll sum[2][sz]; 41#define I inline 42#define R register 43I void Add(R int x,R ll v,R int t){S1+=v*t;while (x<=n+2) sum[t][x]+=v,x+=(x&(-x));} 44I ll Query(R int x,R int t){ll ret=0;while (x) ret+=sum[t][x],x-=(x&(-x));return ret;} 45 46ll ans[sz]; 47int blo; 48int pos[sz]; 49void init(){blo=pow(n,2.0/3);rep(i,1,sz-1) pos[i]=i/blo;} 50struct hh 51{ 52 int l,r,tim,id; 53 I const bool operator < (const hh &a) const 54 { 55 if (pos[l]!=pos[a.l]) return pos[l]<pos[a.l]; 56 if (pos[r]!=pos[a.r]) return pos[r]<pos[a.r]; 57 return tim<a.tim; 58 } 59}q[sz]; 60 61struct hhh 62{ 63 int pos,u,t; // t=0:pre t=1:nxt w[t][pos]->u 64 inline hhh(int Pos=0,int U=0,int T=0){pos=Pos,u=U,t=T;} 65}p[sz*6]; 66 67I void swap(int &x,int &y){int t=x;x=y,y=t;} 68#define add(x) Add(w[0][x]+1,x,0);Add(w[1][x]+1,x,1); 69I void del(R int x){Add(w[0][x]+1,-x,0);Add(w[1][x]+1,-x,1);} 70I void work(R hhh &a,R int l,R int r) 71{ 72 R int pos=a.pos,t=a.t,&W=w[t][pos]; 73 if (l<=pos&&pos<=r) Add(W+1,-pos,t); 74 R int tt=a.u;a.u=W;W=tt; 75 if (l<=pos&&pos<=r) Add(W+1,pos,t); 76} 77 78I int calcPre(R int x,R int col){set<int>::iterator it=s[col].lower_bound(x);--it;return *it;} 79I int calcNxt(R int x,R int col){return *(s[col].upper_bound(x));} 80 81signed main() 82{ 83 srand(time(0));rep(i,1,233) srand(rand()); 84 file(); 85 R int x,y,z; 86 read(n,m); 87 init(); 88 rep(i,1,n) s[i].insert(0),s[i].insert(n+1); 89 rep(i,1,n) read(a[i]),s[a[i]].insert(i); 90 rep(i,1,n) w[0][i]=pre[i]=calcPre(i,a[i]),w[1][i]=nxt[i]=calcNxt(i,a[i]); 91 R int tim=0,c=0; 92 rep(_,1,m) 93 { 94 read(z,x,y); 95 if (z==1) 96 { 97 if (y==a[x]) continue; 98 int Pre=calcPre(x,y),Nxt=calcNxt(x,y); 99 s[a[x]].erase(x);s[y].insert(x); 100 a[x]=y; 101 if (nxt[x]!=n+1) p[++tim]=hhh(nxt[x],pre[x],0),pre[nxt[x]]=pre[x]; 102 if (pre[x]!=0) p[++tim]=hhh(pre[x],nxt[x],1),nxt[pre[x]]=nxt[x]; 103 if (Pre!=0) p[++tim]=hhh(Pre,x,1),nxt[Pre]=x; 104 if (Nxt!=n+1) p[++tim]=hhh(Nxt,x,0),pre[Nxt]=x; 105 pre[x]=Pre;nxt[x]=Nxt; 106 p[++tim]=hhh(x,Pre,0);p[++tim]=hhh(x,Nxt,1); 107 } 108 else ++c,q[c]=(hh){x,y,tim,c}; 109 } 110 sort(q+1,q+c+1); 111 R int l=1,r=0;tim=0; 112 rep(i,1,c) 113 { 114 R int L=q[i].l,RR=q[i].r,Tim=q[i].tim; 115 while (tim<Tim) work(p[++tim],l,r); 116 while (tim>Tim) work(p[tim--],l,r); 117 while (l<L) {Add(w[0][l]+1,-l,0);Add(w[1][l]+1,-l,1);++l;} 118 while (l>L) {--l;Add(w[0][l]+1,l,0);Add(w[1][l]+1,l,1);} 119 while (r<RR) {++r;Add(w[0][r]+1,r,0);Add(w[1][r]+1,r,1);} 120 while (r>RR) {Add(w[0][r]+1,-r,0);Add(w[1][r]+1,-r,1);--r;} 121 ans[q[i].id]=S1-Query(RR+1,1)-Query(L-1+1,0); 122 } 123 rep(i,1,c) printf("%lld\n",ans[i]); 124}
做法三
1#include<bits/stdc++.h> 2namespace my_std{ 3 using namespace std; 4 #define pii pair<int,int> 5 #define fir first 6 #define sec second 7 #define MP make_pair 8 #define rep(i,x,y) for (int i=(x);i<=(y);i++) 9 #define drep(i,x,y) for (int i=(x);i>=(y);i--) 10 #define go(x) for (int i=head[x];i;i=edge[i].nxt) 11 #define sz 101001 12 typedef long long ll; 13 template<typename T> 14 inline void read(T& t) 15 { 16 t=0;char f=0,ch=getchar(); 17 double d=0.1; 18 while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar(); 19 while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar(); 20 if(ch=='.') 21 { 22 ch=getchar(); 23 while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar(); 24 } 25 t=(f?-t:t); 26 } 27 template<typename T,typename... Args> 28 inline void read(T& t,Args&... args){read(t); read(args...);} 29 void file() 30 { 31 #ifndef ONLINE_JUDGE 32 freopen("a.txt","r",stdin); 33 #endif 34 } 35// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;} 36} 37using namespace my_std; 38 39int n,m; 40int a[sz]; 41int pre[sz],nxt[sz]; 42int w[sz]; 43set<int>s[sz]; 44 45ll sum[sz]; 46//void add(int x,ll v){if (!x) return;while (x<=n) sum[x]+=v,x+=(x&(-x));} 47//ll query(int x){ll ret=0;while (x) ret+=sum[x],x-=(x&(-x));return ret;} 48void add(int x,ll v){sum[x]+=v;} 49ll query(int x){ll ret=0;rep(i,1,x) ret+=sum[i];return ret;} 50 51ll ans[sz]; 52int blo; 53int pos[sz]; 54void init(){blo=pow(n,2.0/3);rep(i,1,sz-1) pos[i]=i/blo;} 55struct hh 56{ 57 int l,r,tim,id; 58 const bool operator < (const hh &a) const 59 { 60 if (pos[l]!=pos[a.l]) return pos[l]<pos[a.l]; 61 if (pos[r]!=pos[a.r]) return pos[r]<pos[a.r]; 62 return tim<a.tim; 63 } 64}q[sz]; 65 66struct hhh 67{ 68 int pos,v; // pre[pos] -> v 69 hhh(int Pos=0,int V=0){pos=Pos,v=V;} 70}p[sz*6]; 71 72void add(int x){add(w[x],x-w[x]);} 73void del(int x){add(w[x],w[x]-x);} 74void work(hhh &a,int l,int r) 75{ 76 if (l<=a.pos&&a.pos<=r) add(w[a.pos],w[a.pos]-a.pos); 77 swap(a.v,w[a.pos]); 78 if (l<=a.pos&&a.pos<=r) add(w[a.pos],a.pos-w[a.pos]); 79} 80 81int calcPre(int x,int col){set<int>::iterator it=s[col].lower_bound(x);--it;return *it;} 82int calcNxt(int x,int col){return *(s[col].upper_bound(x));} 83 84 85int main() 86{ 87 file(); 88 int x,y,z; 89 read(n,m); 90 init(); 91 rep(i,1,n) s[i].insert(0),s[i].insert(n+1); 92 rep(i,1,n) read(a[i]),s[a[i]].insert(i); 93 int tim=0,c=0; 94 rep(i,1,n) w[i]=pre[i]=calcPre(i,a[i]),nxt[i]=calcNxt(i,a[i]); 95 while (m--) 96 { 97 read(z,x,y); 98 if (z==1) 99 { 100 if (y==a[x]) continue; 101 int Pre=calcPre(x,y),Nxt=calcNxt(x,y); 102 s[a[x]].erase(x);s[y].insert(x); 103 a[x]=y; 104 if (nxt[x]!=n+1) 105 pre[nxt[x]]=pre[x], 106 p[++tim]=hhh(nxt[x],pre[nxt[x]]); 107 if (pre[x]!=0) nxt[pre[x]]=nxt[x]; 108 if (Pre!=0) nxt[Pre]=x; 109 if (Nxt!=n+1) 110 pre[Nxt]=x, 111 p[++tim]=hhh(Nxt,pre[Nxt]); 112 pre[x]=Pre;nxt[x]=Nxt; 113 p[++tim]=hhh(x,pre[x]); 114 } 115 else ++c,q[c]=(hh){x,y,tim,c}; 116 } 117 sort(q+1,q+c+1); 118 int l=1,r=0;tim=0; 119 rep(i,1,c) 120 { 121 int L=q[i].l,R=q[i].r,Tim=q[i].tim; 122 while (tim<Tim) work(p[++tim],l,r); 123 while (tim>Tim) work(p[tim--],l,r); 124 while (l<L) del(l++); 125 while (l>L) add(--l); 126 while (r<R) add(++r); 127 while (r>R) del(r--); 128 ans[q[i].id]=query(n)-query(L-1); 129 } 130 rep(i,1,c) printf("%lld\n",ans[i]); 131}
做法四
正解比暴力好写多了呢……
1#include<bits/stdc++.h> 2namespace my_std{ 3 using namespace std; 4 #define pii pair<int,int> 5 #define fir first 6 #define sec second 7 #define MP make_pair 8 #define rep(i,x,y) for (int i=(x);i<=(y);i++) 9 #define drep(i,x,y) for (int i=(x);i>=(y);i--) 10 #define go(x) for (int i=head[x];i;i=edge[i].nxt) 11 #define sz 101010 12 typedef long long ll; 13 template<typename T> 14 inline void read(T& t) 15 { 16 t=0;char f=0,ch=getchar(); 17 double d=0.1; 18 while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar(); 19 while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar(); 20 if(ch=='.') 21 { 22 ch=getchar(); 23 while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar(); 24 } 25 t=(f?-t:t); 26 } 27 template<typename T,typename... Args> 28 inline void read(T& t,Args&... args){read(t); read(args...);} 29 void file() 30 { 31 #ifndef ONLINE_JUDGE 32 freopen("a.txt","r",stdin); 33 #endif 34 } 35// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;} 36} 37using namespace my_std; 38 39int n,m,Q; 40int a[sz]; 41int pre[sz],nxt[sz]; 42set<int>s[sz]; 43 44int calcPre(int x,int col){set<int>::iterator it=s[col].lower_bound(x);--it;return *it;} 45int calcNxt(int x,int col){return *(s[col].upper_bound(x));} 46 47ll ans[sz]; 48struct hh 49{ 50 int type; // 0:modify 1:query 51 int x,y,val; 52 int id; 53}q[sz*6]; 54inline bool cmp(const hh &x,const hh &y) 55{ 56 if (x.type!=y.type) return x.type<y.type; 57 if (x.type) return x.y<y.y; 58 return x.x<y.x; 59} 60inline void calc(int x,int v) // pre[x]->v 61{ 62 q[++m]=(hh){0,x,pre[x],pre[x]-x,0}; 63 pre[x]=v; 64 q[++m]=(hh){0,x,v,x-v,0}; 65} 66 67ll sum[sz]; 68void add(int x,ll v){ if (!x) return; while (x<=n) sum[x]+=v,x+=(x&(-x)); } 69ll query(int x){ ll ret=0; while (x) ret+=sum[x],x-=(x&(-x)); return ret; } 70 71void solve(int l,int r) 72{ 73 if (l==r) return; 74 int mid=(l+r)>>1; 75 solve(l,mid);solve(mid+1,r); 76 int p=l-1; 77 rep(i,mid+1,r) if (q[i].type) 78 { 79 while (p<mid&&(q[p+1].type||q[p+1].x<=q[i].y)) 80 { 81 ++p; 82 if (!q[p].type) add(q[p].y,q[p].val); 83 } 84 ans[q[i].id]+=query(n)-query(q[i].x-1); 85 } 86 rep(i,l,p) if (!q[i].type) add(q[i].y,-q[i].val); 87 sort(q+l,q+r+1,cmp); 88} 89 90int main() 91{ 92 file(); 93 int x,y,z; 94 read(n,Q); 95 rep(i,1,n) s[i].insert(0),s[i].insert(n+1); 96 rep(i,1,n) read(a[i]),s[a[i]].insert(i); 97 rep(i,1,n) pre[i]=calcPre(i,a[i]),nxt[i]=calcNxt(i,a[i]),q[++m]=(hh){0,i,pre[i],i-pre[i],0}; 98 int c=0; 99 while (Q--) 100 { 101 read(z,x,y); 102 if (z==1) 103 { 104 if (y==a[x]) continue; 105 int Pre=calcPre(x,y),Nxt=calcNxt(x,y); 106 s[a[x]].erase(x);s[y].insert(x); 107 a[x]=y; 108 if (nxt[x]!=n+1) calc(nxt[x],pre[x]); 109 if (pre[x]!=0) nxt[pre[x]]=nxt[x]; 110 if (Pre!=0) nxt[Pre]=x; 111 if (Nxt!=n+1) calc(Nxt,x); 112 calc(x,Pre); 113 nxt[x]=Nxt; 114 } 115 else ++c,q[++m]=(hh){1,x,y,0,c}; 116 } 117 solve(1,m); 118 rep(i,1,c) printf("%lld\n",ans[i]); 119 return 0; 120}