uoj 218 火车管理-白红宇

uoj 218 火车管理

阅读量：4703 次

发布时间：2019-06-10

本文共 2718 字，大约阅读时间需要 9 分钟。

题目大意：

事件可以概括成一下三种

1 l r 求l-r区间内栈顶火车的权值和

2 l 删除l火车站的栈顶若没有火车则不操作

3 l r x 在l-r区间内的每个火车站加入一个权值为x的火车

思路：

维护一颗主席树维护区间sum以及该版本内每个点是哪个版本的

对于1操作直接query即可

对于2操作找到当前l点的版本单点修改为查询结果-1的那个版本

对于3操作区间修改

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              10 #define inf 213906214311 #define ll long long12 #define MAXN 50010013 using namespace std;14 inline int read()15 {16 int x=0,f=1;char ch=getchar();17 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}19 return x*f;20 }21 int n,m,ch,rt[MAXN],las,val[MAXN],cnt;22 struct node { int ls,rs,val,sum;}tr[MAXN<<7];23 void pshd(int k,int l,int r,int mid)24 {25 tr[++cnt]=tr[tr[k].ls],tr[cnt].val=tr[k].val,tr[cnt].sum=val[tr[k].val]*(mid-l+1),tr[k].ls=cnt;26 tr[++cnt]=tr[tr[k].rs],tr[cnt].val=tr[k].val,tr[cnt].sum=val[tr[k].val]*(r-mid),tr[k].rs=cnt;27 tr[k].val=0;28 }29 int querylas(int k,int l,int r,int x)30 {31 if(l==r) return tr[k].val;32 int mid=(l+r)>>1;33 if(tr[k].val) pshd(k,l,r,mid);34 if(x<=mid) return querylas(tr[k].ls,l,mid,x);35 else return querylas(tr[k].rs,mid+1,r,x);36 }37 int query(int k,int l,int r,int a,int b)38 {39 if(l==a&&r==b) return tr[k].sum;40 int mid=(l+r)>>1;41 if(tr[k].val) pshd(k,l,r,mid);42 if(b<=mid) return query(tr[k].ls,l,mid,a,b);43 else if(a>mid) return query(tr[k].rs,mid+1,r,a,b);44 else return query(tr[k].ls,l,mid,a,mid)+query(tr[k].rs,mid+1,r,mid+1,b);45 }46 void mdf(int &k,int kk,int l,int r,int a,int b,int x)47 {48 if(!k) k=++cnt,tr[k]=tr[kk];49 if(l==a&r==b) {tr[k].sum=(r-l+1)*val[x],tr[k].val=x;return ;}50 int mid=(l+r)>>1,ok=tr[k].val;51 if(tr[k].val) pshd(k,l,r,mid);52 if(b<=mid) { if(!ok) tr[k].ls=0;mdf(tr[k].ls,tr[kk].ls,l,mid,a,b,x);}53 else if(a>mid) { if(!ok) tr[k].rs=0;mdf(tr[k].rs,tr[kk].rs,mid+1,r,a,b,x);}54 else { if(!ok) tr[k].ls=tr[k].rs=0;mdf(tr[k].ls,tr[kk].ls,l,mid,a,mid,x);mdf(tr[k].rs,tr[kk].rs,mid+1,r,mid+1,b,x);}55 tr[k].sum=tr[tr[k].ls].sum+tr[tr[k].rs].sum;56 }57 int main()58 {59 n=read(),m=read(),ch=read();int x,y,z,t;60 for(int i=1;i<=m;i++)61 {62 z=read();rt[i]=++cnt,tr[rt[i]]=tr[rt[i-1]];63 if(z==1) {x=(read()+las*ch)%n+1,y=(read()+las*ch)%n+1;printf("%d\n",las=query(rt[i],1,n,min(x,y),max(x,y)));}64 if(z==2) {x=(read()+las*ch)%n+1,y=querylas(rt[i],1,n,x);if(y) mdf(rt[i],rt[i-1],1,n,x,x,querylas(rt[y-1],1,n,x));}65 if(z==3) {x=(read()+las*ch)%n+1,y=(read()+las*ch)%n+1,val[i]=read();mdf(rt[i],rt[i-1],1,n,min(x,y),max(x,y),i);}66 }67 }