题目描述
uoj 旗下有一个火车站，用来管理属于 uoj 的小火车。
火车站一共有 nn 条编号为 1,…,n1,…,n 的，只有一端的用来存放小火车的铁路，由于小火车特殊的构造，每条铁路可以停放无数辆小火车。每条铁路是相互独立的。
铁路是一个栈结构，后停放的小火车可以先出来。
每辆小火车有一个吨位 tt。
由于 NOI2016 即将到来，想要跟小火车正面作战的人多了起来，火车站管理员九条可怜每天需要处理很多事件。
事件可以概括成一下三种：
1 l r有人想跟铁路编号在 [l,r][l,r] 的每条铁路的第一辆可以开出来的小火车正面战斗，你需要统计这些小火车的吨位之和，没有火车的铁路不计入答案。2 l编号为 ll 的铁路开走一辆火车，如果这条铁路没有小火车则不开出。3 l r x铁路编号在 [l,r][l,r] 的每条铁路都新停放一辆吨位为 xx 的火车。
现在管理员九条可怜要去南海前线了，你需要替他管理火车站。
由于火车站很忙，所以你需要实时反馈信息，我们会用一些手段要求你强制在线，具体请看输入格式。
题解
第一个和第三个操作都是基本的线段树操作，第二个操作我们可以把它看做返回该元素的上一个版本，不难想到用主席树去维护。
我们在可持久化线段树上维护两个信息，当前节点的版本和当前区间的权值，这个版本标记我们可以把它看做lazy标记，每次访问的时候下放即可。
注意，因为是可持久化线段树，标记也要可持久化，每次下放标记时要新建节点。
代码
#include<iostream> #include<cstdio> #define N 500009 using namespace std; typedef long long ll; int tot,n,m,type,opt,l,r,T[N]; ll x,ans,val[N]; inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } struct segment{int rs,ls,la;ll sum;}tr[N*80]; inline int newnode(int pre){int now=++tot;tr[now]=tr[pre];return now;} inline void pushdown(int cnt,int l1,int l2){ tr[cnt].ls=newnode(tr[cnt].ls); tr[tr[cnt].ls].la=tr[cnt].la; tr[tr[cnt].ls].sum=1ll*val[tr[cnt].la]*l1; tr[cnt].rs=newnode(tr[cnt].rs); tr[tr[cnt].rs].la=tr[cnt].la; tr[tr[cnt].rs].sum=1ll*val[tr[cnt].la]*l2; tr[cnt].la=0; } void upd(int &cnt,int l,int r,int L,int R,int x){ if(l>=L&&r<=R){tr[cnt].la=x;tr[cnt].sum=1ll*(r-l+1)*val[x];return;} int mid=(l+r)>>1; int tag=0; if(tr[cnt].la)pushdown(cnt,mid-l+1,r-mid),tag=1; if(mid>=L){ if(!tag)tr[cnt].ls=newnode(tr[cnt].ls); upd(tr[cnt].ls,l,mid,L,R,x); } if(mid<R){ if(!tag)tr[cnt].rs=newnode(tr[cnt].rs); upd(tr[cnt].rs,mid+1,r,L,R,x); } tr[cnt].sum=tr[tr[cnt].ls].sum+tr[tr[cnt].rs].sum; } int query_id(int cnt,int l,int r,int x){ if(l==r)return tr[cnt].la; int mid=(l+r)>>1; if(tr[cnt].la)pushdown(cnt,mid-l+1,r-mid); if(mid>=x)return query_id(tr[cnt].ls,l,mid,x); else return query_id(tr[cnt].rs,mid+1,r,x); } ll query_sum(int cnt,int l,int r,int L,int R){ if(l>=L&&r<=R)return tr[cnt].sum; int mid=(l+r)>>1; if(tr[cnt].la)pushdown(cnt,mid-l+1,r-mid); ll ans=0; if(mid>=L)ans+=query_sum(tr[cnt].ls,l,mid,L,R); if(mid<R)ans+=query_sum(tr[cnt].rs,mid+1,r,L,R); return ans; } int main(){ n=rd();m=rd();type=rd(); for(int i=1;i<=m;++i){ opt=rd(); T[i]=newnode(T[i-1]); if(opt==1){ l=rd();r=rd(); l=(l+type*ans)%n+1; r=(r+type*ans)%n+1;if(l>r)swap(l,r); printf("%lld ",ans=query_sum(T[i],1,n,l,r)); } else if(opt==2){ l=rd();l=(l+type*ans)%n+1; int id=query_id(T[i],1,n,l); if(id)upd(T[i],1,n,l,l,query_id(T[id-1],1,n,l)); } else{ l=rd();r=rd();x=rd(); l=(l+type*ans)%n+1; r=(r+type*ans)%n+1;if(l>r)l^=r^=l^=r; val[i]=x; upd(T[i],1,n,l,r,i); } } return 0; }