http://uoj.ac/problem/218
思路:建立一个可持久化线段树，代表这个位置的火车是哪辆，然后再弄一个线段树维护答案。
如果询问，直接询问线段树。
如果区间压入，直接在主席树上面压入，然后更新线段树答案
如果弹出，那么直接找主席树当前位之前的火车是那辆，然后修改线段树答案，再修改当前主席树答案。
改题的时候蜜汁错误。。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
int tr[],ls[],tag[],rs[];
int tg[],sum[],sz,rt[],a[];
int n,m,ty;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void pushdown(int k){
if (tag[k]==-) return;
if (!ls[k]) ls[k]=++sz;
if (!rs[k]) rs[k]=++sz;
tag[ls[k]]=tag[rs[k]]=tr[ls[k]]=tr[rs[k]]=tag[k];
tag[k]=-;
}
void add(int &k,int kk,int l,int r,int x,int y,int v){
k=++sz;tag[k]=-;
if (x==l&&r==y){
tag[k]=tr[k]=v;
return;
}
pushdown(kk);
int mid=(l+r)>>;
ls[k]=ls[kk];rs[k]=rs[kk];
if (y<=mid) add(ls[k],ls[kk],l,mid,x,y,v);
else
if (x>mid) add(rs[k],rs[kk],mid+,r,x,y,v);
else
add(ls[k],ls[kk],l,mid,x,mid,v),add(rs[k],rs[kk],mid+,r,mid+,y,v);
}
int query(int k,int l,int r,int pos){
if (!k||l==r) return tr[k];
pushdown(k);
int mid=(l+r)>>;
if (pos<=mid) return query(ls[k],l,mid,pos);
else return query(rs[k],mid+,r,pos);
}
void pushdown(int k,int l,int r){
if (tg[k]==-||l==r) return;
tg[k*]=tg[k*+]=tg[k];
int mid=(l+r)>>;
sum[k*]=tg[k]*(mid-l+);
sum[k*+]=tg[k]*(r-mid);
tg[k]=-;
}
void modify(int k,int l,int r,int x,int y,int v){
pushdown(k,l,r);
if (x==l&&r==y){
tg[k]=v;sum[k]=(r-l+)*v;
pushdown(k,l,r);
return;
}
int mid=(l+r)>>;
if (y<=mid) modify(k*,l,mid,x,y,v);
else
if (x>mid) modify(k*+,mid+,r,x,y,v);
else modify(k*,l,mid,x,mid,v),modify(k*+,mid+,r,mid+,y,v);
sum[k]=sum[k*]+sum[k*+];
}
int getsum(int k,int l,int r,int x,int y){
pushdown(k,l,r);
if (x==l&&r==y){
return sum[k];
}
int mid=(l+r)>>,z=;
if (y<=mid) return getsum(k*,l,mid,x,y);
else
if (x>mid) return getsum(k*+,mid+,r,x,y);
else return getsum(k*,l,mid,x,mid)+getsum(k*+,mid+,r,mid+,y);
}
int main(){
n=read();m=read();ty=read();
int ans=;
for (int i=;i<=m;i++){
rt[i]=rt[i-];
int opt=read(),l=read();l=(l+ty*ans)%n+;
if (opt==){
int x=query(rt[i],,n,l);
if (x){
int y=query(rt[x-],,n,l);
add(rt[i],rt[i],,n,l,l,y);
modify(,,n,l,l,a[y]);
}
continue;
}
int r=read();r=(r+ty*ans)%n+;
if (l>r) std::swap(l,r);
if (opt==){printf("%d\n",ans=getsum(,,n,l,r));}
else{
a[i]=read();
add(rt[i],rt[i],,n,l,r,i);
modify(,,n,l,r,a[i]);
}
}
return ;
}