题目描述

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
     
      #include
      
       #define N 500009using 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
       
        >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)swap(l,r);          printf("%lld\n",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;}