【UNR #1】火车管理（主席树）
好好的代码被 \(extra\ test\) 卡常了。。。我就放一个目前最快的版本吧。。。
题意简化：
有 \(n\) 个栈，\(m\) 次操作。
将 \(x\) 压入 \([l,r]\) 的栈中
将 \(l\) 的栈顶弹出
询问 \([l,r]\) 栈顶的和
\(n,m\leq 5\times 10^5\)
虽然最优解是神仙二叉树，我只会主席树的解法。。。
显然 \(1,3\) 操作用一棵线段树就够了，\(2\) 操作需要另外一棵主席树，并且在历史版本上修改。
\(Code\ Below:\)
#include <bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
int n,m,k,a[maxn];
namespace IO{
#define gc() (iS==iT?(iT=(iS=ibuff)+fread(ibuff,1,SIZ,stdin),(iS==iT?EOF:*iS++)):*iS++)
const int SIZ=1<<21|1;
char *iS,*iT,ibuff[SIZ],obuff[SIZ],*oS=obuff,*oT=oS+SIZ-1,fu[110],c;int fr;
inline void out(){
fwrite(obuff,1,oS-obuff,stdout);
oS=obuff;
}
template <class T>
inline void read(T &x){
x=0;T y=1;
for(c=gc();(c>'9'||c<'0')&&c!='-';c=gc());
c=='-'?y=-1:x=(c&15);
for(c=gc();c>='0'&&c<='9';c=gc()) x=x*10+(c&15);
x*=y;
}
template <class T>
inline void print(T x,char text='\n'){
if(x<0) *oS++='-',x*=-1;
if(x==0) *oS++='0';
while(x) fu[++fr]=x%10+'0',x/=10;
while(fr) *oS++=fu[fr--];
*oS++=text;out();
}
}
struct President_Tree{
#define rt(x) PT.rt[x]
struct node{
int sum,lazy,ls,rs;
}t[maxn*80];
int rt[maxn],cnt;
inline void pushdown(int x){
if(t[x].lazy){
if(!t[x].ls) t[x].ls=++cnt;
if(!t[x].rs) t[x].rs=++cnt;
t[t[x].ls].sum=t[t[x].rs].sum=t[t[x].ls].lazy=t[t[x].rs].lazy=t[x].lazy;
t[x].lazy=0;
}
}
inline void update(int &x,int y,int L,int R,int C,int l,int r){
x=++cnt;
if(L <= l && r <= R){t[x].sum=t[x].lazy=C;return;}
pushdown(y);t[x].ls=t[y].ls;t[x].rs=t[y].rs;
int mid=(l+r)>>1;
if(L <= mid) update(t[x].ls,t[y].ls,L,R,C,l,mid);
if(R > mid) update(t[x].rs,t[y].rs,L,R,C,mid+1,r);
}
inline int query(int x,int l,int r,int k){
if(l == r) return t[x].sum;
pushdown(x);
int mid=(l+r)>>1;
if(k <= mid) return query(t[x].ls,l,mid,k);
else return query(t[x].rs,mid+1,r,k);
}
}PT;
struct Segment_Tree{
#define lson (rt<<1)
#define rson (rt<<1|1)
int sum[maxn<<2],lazy[maxn<<2];
inline void pushup(int rt){sum[rt]=sum[lson]+sum[rson];}
inline void pushdown(int rt,int len){
if(lazy[rt]){
sum[lson]=(len-(len>>1))*lazy[rt];
sum[rson]=(len>>1)*lazy[rt];
lazy[lson]=lazy[rson]=lazy[rt];
lazy[rt]=0;
}
}
inline void update(int L,int R,int C,int l,int r,int rt){
if(L <= l && r <= R){
sum[rt]=(r-l+1)*C;lazy[rt]=C;
return ;
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
if(L <= mid) update(L,R,C,l,mid,lson);
if(R > mid) update(L,R,C,mid+1,r,rson);
pushup(rt);
}
inline int query(int L,int R,int l,int r,int rt){
if(L <= l && r <= R) return sum[rt];
pushdown(rt,r-l+1);
int mid=(l+r)>>1,ans=0;
if(L <= mid) ans+=query(L,R,l,mid,lson);
if(R > mid) ans+=query(L,R,mid+1,r,rson);
return ans;
}
}ST;
int main()
{
IO::read(n),IO::read(m),IO::read(k);
int op,l,r,x,y,lastans=0;
for(int i=1;i<=n;i++){
rt(i)=rt(i-1);
IO::read(op);
if(op==1){
IO::read(l),IO::read(r);
l=(l+k*lastans)%n+1;
r=(r+k*lastans)%n+1;
if(l>r) swap(l,r);
IO::print(lastans=ST.query(l,r,1,n,1));
}
if(op==2){
IO::read(l);
l=(l+k*lastans)%n+1;
x=PT.query(rt(i),1,n,l);
if(x){
y=PT.query(rt(x-1),1,n,l);
PT.update(rt(i),rt(i),l,l,y,1,n);
ST.update(l,l,a[y],1,n,1);
}
}
if(op==3){
IO::read(l),IO::read(r);
l=(l+k*lastans)%n+1;
r=(r+k*lastans)%n+1;
if(l>r) swap(l,r);
IO::read(x);a[i]=x;
PT.update(rt(i),rt(i),l,r,i,1,n);
ST.update(l,r,x,1,n,1);
}
}
return 0;
}