洛谷
Codeforces
这题我写了四种做法……
思路
不管做法怎样，思路都是一样的。
好吧，其实不一样，有细微的差别。
第一种
考虑位置\(x\)对区间\([l,r]\)有\(\pm x\)的贡献当且仅当\(pre_x\!\!\!r\)，其中\(pre,nxt\)表示与\(x\)同种颜色的前驱后继。
那么题目就转化为二维数点了：一维是位置，一维是前驱/后继，权值是\(\pm?\)位置。
第二种
考虑最后的减去开始的等价于每一位减去前面的。
即位置\(x\)的贡献是\(x-pre_x,pre_x\geq l\)。
那么题目同样转化为二维数点：一维是位置，一维是前驱，权值是\(x-pre_x\)。
做法
做法一
按照第一种思路，暴力树套树。
然而这样你会发现自己要么MLE要么RE……
做法二
按照第一种思路，莫队+树状数组。
然而你会不停地TLE，而且我的卡常技巧不够高超，放弃了。
做法三
按照第二种思路，莫队+树状数组。
并不需要怎么卡常就可以过。
嘿嘿，之前卡我莫队，这次我卡你评测。
放几张图给大家瞧瞧：
中间那个25的是我的，其他是被我卡的/滑稽
做法四
这个是正解了。CDQ分治+二维数点。
但是太晚了，不想写
留坑
代码
做法一
#includenamespace my_std{ using namespace std; #define pii pair #define fir first #define sec second #define MP make_pair #define rep(i,x,y) for (int i=(x);i<=(y);i++) #define drep(i,x,y) for (int i=(x);i>=(y);i--) #define go(x) for (int i=head[x];i;i=edge[i].nxt) #define sz 101010 typedef long long ll; template inline void read(Tchar f=0,ch=getchar(); double d=0.1; while(ch>‘9‘||ch<‘0‘) f|=(ch==‘-‘),ch=getchar(); while(ch=‘0‘) t=t*10+ch-48,ch=getchar(); if(ch==‘.‘) { ch=getchar(); while(ch=‘0‘) t+=d*(ch^48),d*=0.1,ch=getchar(); } t=(f?-t:t); } template inline void read(T read(args...);} void file() { #ifndef ONLINE_JUDGE freopen("a.txt","r",stdin); #endif }// 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;}}using namespace my_std;int n,m;int a[sz];int pre[sz],nxt[sz];sets[sz];#define Tree sz*100int Ls[Tree],Rs[Tree];ll sum[2][Tree]; // 0:pre 1:nxt#define Lson Ls[k],l,mid#define Rson Rs[k],mid+1,rint cnt;int bin[Tree],top;void del(int bin[++top]=k;k=0;}int newnode(){return top?bin[top--]:++cnt;}void Add(int sum[t][k]+=y; if (l==r) { if (!sum[0][k] return; } int mid=(l+r)>>1; if (x<=mid) Add(Lson,x,y,t); else Add(Rson,x,y,t); if (!sum[0][k]}ll Query(int k,int l,int r,int x,int y,int t){ if (!k||x>y||!sum[t][k]) return 0; if (x<=l int mid=(l+r)>>1;ll ret=0; if (x<=mid) ret+=Query(Lson,x,y,t); if (y>mid) ret+=Query(Rson,x,y,t); return ret;}void Debug(int k,int l,int r,int t){ if (!k) { rep(i,l,r) printf("0 "); return; } if (l==r) return (void)printf("%lld ",sum[t][k]); int mid=(l+r)>>1; rep(i,0,1) assert(sum[i][k]==sum[i][Ls[k]]+sum[i][Rs[k]]); Debug(Lson,t);Debug(Rson,t);}#undef Lson#undef Rsonint root[sz<<2];#define ls k<<1#define rs k<<1|1#define lson ls,l,mid#define rson rs,mid+1,rll query(int k,int l,int r,int x,int y){ if (x<=l return a-b; } int mid=(l+r)>>1;ll ret=0; if (x<=mid) ret+=query(lson,x,y); if (y>mid) ret+=query(rson,x,y); return ret;}void debug(int k,int l,int r){ printf("%d ~ %d:\n",l,r); printf("pre: ");Debug(root[k],0,n+1,0);puts(""); printf("nxt: ");Debug(root[k],0,n+1,1);puts(""); if (l==r) return; int mid=(l+r)>>1; debug(lson);debug(rson);}void change(int k,int l,int r,int x,int a,int b) // pre[x]->a , nxt[x]->b{ if (pre[x]!=-1) Add(root[k],0,n+1,pre[x],-x,0); Add(root[k],0,n+1,a,x,0); if (nxt[x]!=-1) Add(root[k],0,n+1,nxt[x],-x,1); Add(root[k],0,n+1,b,x,1); if (l==r) return; int mid=(l+r)>>1; if (x<=mid) change(lson,x,a,b); else change(rson,x,a,b);}int calcPre(int x,int col){set::iterator it=s[col].lower_bound(x);--it;return *it;}int calcNxt(int x,int col){return *(s[col].upper_bound(x));}int main(){ file(); int x,y,z; read(n,m); rep(i,1,n) s[i].insert(0),s[i].insert(n+1); rep(i,1,n) read(a[i]),s[a[i]].insert(i); rep(i,1,n) { int Pre=calcPre(i,a[i]),Nxt=calcNxt(i,a[i]); pre[i]=nxt[i]=-1; change(1,1,n,i,Pre,Nxt); pre[i]=Pre,nxt[i]=Nxt; } while (m--) { read(z,x,y); if (z==1) { if (y==a[x]) continue; int Pre=calcPre(x,y),Nxt=calcNxt(x,y); change(1,1,n,x,Pre,Nxt); if (pre[x]!=0) change(1,1,n,pre[x],pre[pre[x]],nxt[x]); if (nxt[x]!=n+1) change(1,1,n,nxt[x],pre[x],nxt[nxt[x]]); if (Pre!=0) change(1,1,n,Pre,pre[Pre],x); if (Nxt!=n+1) change(1,1,n,Nxt,x,nxt[Nxt]); s[a[x]].erase(x);s[y].insert(x); a[x]=y; if (nxt[x]!=n+1) pre[nxt[x]]=pre[x]; if (pre[x]!=0) nxt[pre[x]]=nxt[x]; if (Pre!=0) nxt[Pre]=x; if (Nxt!=n+1) pre[Nxt]=x; pre[x]=Pre;nxt[x]=Nxt; } else printf("%lld\n",query(1,1,n,x,y)); }}
做法二
代码被我瞎卡一波常数之后变得巨丑无比。
#includenamespace my_std{ using namespace std; #define rep(i,x,y) for (R int i=x;i<=y;++i) #define sz 101001 typedef long long ll; template inline void read(Tchar f=0,ch=getchar(); double d=0.1; while(ch>‘9‘||ch<‘0‘) f|=(ch==‘-‘),ch=getchar(); while(ch=‘0‘) t=t*10+ch-48,ch=getchar(); if(ch==‘.‘) { ch=getchar(); while(ch=‘0‘) t+=d*(ch^48),d*=0.1,ch=getchar(); } t=(f?-t:t); } template inline void read(T read(args...);} void file() { #ifndef ONLINE_JUDGE freopen("a.txt","r",stdin); #endif }// 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;}}using namespace my_std;int n,m;int a[sz];int pre[sz],nxt[sz];int w[2][sz]; // 0:pre 1:nxtsets[sz];ll S1;ll sum[2][sz];#define I inline#define R registerI void Add(R int x,R ll v,R int t){S1+=v*t;while (x<=n+2) sum[t][x]+=v,x+=(x}I ll Query(R int x,R int t){ll ret=0;while (x) ret+=sum[t][x],x-=(xreturn ret;}ll ans[sz];int blo;int pos[sz];void init(){blo=pow(n,2.0/3);rep(i,1,sz-1) pos[i]=i/blo;}struct hh{ int l,r,tim,id; I const bool operator <(const hh }}p[sz*6];I void swap(int x=y,y=t;}#define add(x) Add(w[0][x]+1,x,0);Add(w[1][x]+1,x,1);I void del(R int x){Add(w[0][x]+1,-x,0);Add(w[1][x]+1,-x,1);}I void work(R hhh if (l<=pos R int tt=a.u;a.u=W;W=tt; if (l<=pos}I int calcPre(R int x,R int col){set::iterator it=s[col].lower_bound(x);--it;return *it;}I int calcNxt(R int x,R int col){return *(s[col].upper_bound(x));}signed main(){ srand(time(0));rep(i,1,233) srand(rand()); file(); R int x,y,z; read(n,m); init(); rep(i,1,n) s[i].insert(0),s[i].insert(n+1); rep(i,1,n) read(a[i]),s[a[i]].insert(i); rep(i,1,n) w[0][i]=pre[i]=calcPre(i,a[i]),w[1][i]=nxt[i]=calcNxt(i,a[i]); R int tim=0,c=0; rep(_,1,m) { read(z,x,y); if (z==1) { if (y==a[x]) continue; int Pre=calcPre(x,y),Nxt=calcNxt(x,y); s[a[x]].erase(x);s[y].insert(x); a[x]=y; if (nxt[x]!=n+1) p[++tim]=hhh(nxt[x],pre[x],0),pre[nxt[x]]=pre[x]; if (pre[x]!=0) p[++tim]=hhh(pre[x],nxt[x],1),nxt[pre[x]]=nxt[x]; if (Pre!=0) p[++tim]=hhh(Pre,x,1),nxt[Pre]=x; if (Nxt!=n+1) p[++tim]=hhh(Nxt,x,0),pre[Nxt]=x; pre[x]=Pre;nxt[x]=Nxt; p[++tim]=hhh(x,Pre,0);p[++tim]=hhh(x,Nxt,1); } else ++c,q[c]=(hh){x,y,tim,c}; } sort(q+1,q+c+1); R int l=1,r=0;tim=0; rep(i,1,c) { R int L=q[i].l,RR=q[i].r,Tim=q[i].tim; while (tim #includenamespace my_std{ using namespace std; #define pii pair #define fir first #define sec second #define MP make_pair #define rep(i,x,y) for (int i=(x);i<=(y);i++) #define drep(i,x,y) for (int i=(x);i>=(y);i--) #define go(x) for (int i=head[x];i;i=edge[i].nxt) #define sz 101001 typedef long long ll; template inline void read(Tchar f=0,ch=getchar(); double d=0.1; while(ch>‘9‘||ch<‘0‘) f|=(ch==‘-‘),ch=getchar(); while(ch=‘0‘) t=t*10+ch-48,ch=getchar(); if(ch==‘.‘) { ch=getchar(); while(ch=‘0‘) t+=d*(ch^48),d*=0.1,ch=getchar(); } t=(f?-t:t); } template inline void read(T read(args...);} void file() { #ifndef ONLINE_JUDGE freopen("a.txt","r",stdin); #endif }// 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;}}using namespace my_std;int n,m;int a[sz];int pre[sz],nxt[sz];int w[sz]; sets[sz];ll sum[sz];//void add(int x,ll v){if (!x) return;while (x<=n) sum[x]+=v,x+=(x}//ll query(int x){ll ret=0;while (x) ret+=sum[x],x-=(xreturn ret;}void add(int x,ll v){sum[x]+=v;}ll query(int x){ll ret=0;rep(i,1,x) ret+=sum[i];return ret;}ll ans[sz];int blo;int pos[sz];void init(){blo=pow(n,2.0/3);rep(i,1,sz-1) pos[i]=i/blo;}struct hh{ int l,r,tim,id; const bool operator <(const hh }}p[sz*6];void add(int x){add(w[x],x-w[x]);}void del(int x){add(w[x],w[x]-x);}void work(hhh swap(a.v,w[a.pos]); if (l<=a.pos}int calcPre(int x,int col){set::iterator it=s[col].lower_bound(x);--it;return *it;}int calcNxt(int x,int col){return *(s[col].upper_bound(x));}int main(){ file(); int x,y,z; read(n,m); init(); rep(i,1,n) s[i].insert(0),s[i].insert(n+1); rep(i,1,n) read(a[i]),s[a[i]].insert(i); int tim=0,c=0; rep(i,1,n) w[i]=pre[i]=calcPre(i,a[i]),nxt[i]=calcNxt(i,a[i]); while (m--) { read(z,x,y); if (z==1) { if (y==a[x]) continue; int Pre=calcPre(x,y),Nxt=calcNxt(x,y); s[a[x]].erase(x);s[y].insert(x); a[x]=y; if (nxt[x]!=n+1) pre[nxt[x]]=pre[x], p[++tim]=hhh(nxt[x],pre[nxt[x]]); if (pre[x]!=0) nxt[pre[x]]=nxt[x]; if (Pre!=0) nxt[Pre]=x; if (Nxt!=n+1) pre[Nxt]=x, p[++tim]=hhh(Nxt,pre[Nxt]); pre[x]=Pre;nxt[x]=Nxt; p[++tim]=hhh(x,pre[x]); } else ++c,q[c]=(hh){x,y,tim,c}; } sort(q+1,q+c+1); int l=1,r=0;tim=0; rep(i,1,c) { int L=q[i].l,R=q[i].r,Tim=q[i].tim; while (tim 留坑 【感谢龙石为本站提供数据质量管理系统,http://www.longshidata.com/pages/quality.html】
做法三
做法四