题目描述
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=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
struct segment{int rs,ls,la;ll sum;}tr[N*];
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=;
}
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+)*val[x];return;}
int mid=(l+r)>>;
int tag=;
if(tr[cnt].la)pushdown(cnt,mid-l+,r-mid),tag=;
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+,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)>>;
if(tr[cnt].la)pushdown(cnt,mid-l+,r-mid);
if(mid>=x)return query_id(tr[cnt].ls,l,mid,x);
else return query_id(tr[cnt].rs,mid+,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)>>;
if(tr[cnt].la)pushdown(cnt,mid-l+,r-mid);
ll ans=;
if(mid>=L)ans+=query_sum(tr[cnt].ls,l,mid,L,R);
if(mid<R)ans+=query_sum(tr[cnt].rs,mid+,r,L,R);
return ans;
}
int main(){
n=rd();m=rd();type=rd();
for(int i=;i<=m;++i){
opt=rd();
T[i]=newnode(T[i-]);
if(opt==){
l=rd();r=rd();
l=(l+type*ans)%n+;
r=(r+type*ans)%n+;if(l>r)swap(l,r);
printf("%lld\n",ans=query_sum(T[i],,n,l,r));
}
else if(opt==){
l=rd();l=(l+type*ans)%n+;
int id=query_id(T[i],,n,l);
if(id)upd(T[i],,n,l,l,query_id(T[id-],,n,l));
}
else{
l=rd();r=rd();x=rd();
l=(l+type*ans)%n+;
r=(r+type*ans)%n+;if(l>r)l^=r^=l^=r;
val[i]=x;
upd(T[i],,n,l,r,i);
}
}
return ;
}