维护一颗主席树
火车入栈相当于区间修改，弹栈相当于返回历史版本
维护线段树区间求和
PS：之前没把代码放上来
extra的最后一个点RE，orz蒟蒻无能为力
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> const int maxn = 600005; const int maxm = 40000007; int tt[maxm],ls[maxm],tag[maxm],rs[maxm]; int tg[maxn<<2],sum[maxn<<2],sz,rt[maxn<<1],a[maxn<<1]; int n,m,ty; int read(){ int t=0,f=1;char c=getchar(); while (c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();} while ('0'<=c&&c<='9'){t=t*10+c-'0';c=getchar();} return t*f; } void merge(int k) { if (tag[k]==-1) return; if (!ls[k]) ls[k]=++sz; if (!rs[k]) rs[k]=++sz; tag[ls[k]]=tag[rs[k]]=tt[ls[k]]=tt[rs[k]]=tag[k]; tag[k]=-1; } void modify(int &k,int l,int r,int rt,int tl,int tr,int v){ k=++sz;tag[k]=-1; if (tl<=l&&tr>=r){ tag[k]=tt[k]=v; return; } merge(rt); int mid=(l+r)>>1; ls[k]=ls[rt];rs[k]=rs[rt]; if(mid>=tl)modify(ls[k],l,mid,ls[rt],tl,tr,v); if(mid<tr)modify(rs[k],mid+1,r,rs[rt],tl,tr,v); } int query(int l,int r,int rt,int pos){ if(!rt||l==r) return tt[rt]; merge(rt); int mid=(l+r)>>1; if(pos<=mid) return query(l,mid,ls[rt],pos); else return query(mid+1,r,rs[rt],pos); } void pushdown(int l,int r,int rt){ if(tg[rt]==-1||l==r) return; tg[rt<<1]=tg[rt<<1|1]=tg[rt]; int mid=(l+r)>>1; sum[rt<<1]=tg[rt]*(mid-l+1); sum[rt<<1|1]=tg[rt]*(r-mid); tg[rt]=-1; } void modify2(int l,int r,int rt,int tl,int tr,int v){ pushdown(l,r,rt); if(tl<=l&&tr>=r){ tg[rt]=v;sum[rt]=(r-l+1)*v; pushdown(l,r,rt); return; } int mid=(l+r)>>1; if(mid>=tl)modify2(l,mid,rt<<1,tl,tr,v); if(mid<tr)modify2(mid+1,r,rt<<1|1,tl,tr,v); sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } int getsum(int l,int r,int rt,int tl,int tr){ pushdown(l,r,rt); if(tl<=l&&tr>=r){ return sum[rt]; } int mid=(l+r)>>1; int ret=0; if(mid>=tl)ret+=getsum(l,mid,rt<<1,tl,tr); if(tr>mid)ret+=getsum(mid+1,r,rt<<1|1,tl,tr); return ret; } int main(){ n=read();m=read();ty=read(); int ans=0; for(int i=1;i<=m;i++){ rt[i]=rt[i-1]; int opt=read(),l=read();l=(l+ty*ans)%n+1; if (opt==1) { int r=read();r=(r+ty*ans)%n+1; if (l>r) std::swap(l,r); printf("%d ",ans=getsum(1,n,1,l,r)); } else if (opt==2){ int x=query(1,n,rt[i],l); if(x){ int y=query(1,n,rt[x-1],l); modify(rt[i],1,n,rt[i],l,l,y); modify2(1,n,1,l,l,a[y]); } continue; } else{ int r=read();r=(r+ty*ans)%n+1; if (l>r) std::swap(l,r); a[i]=read(); modify(rt[i],1,n,rt[i],l,r,i); modify2(1,n,1,l,r,a[i]); } } return 0; }