建一棵答案线段树存栈顶值，两棵可持久化线段树分别存栈顶值和栈顶元素入栈时间

询问就直接在答案线段树上查，弹栈就用入栈时间在对应版本的可持久化线段树上查询即可，修改就是可持久化线段树的区间覆盖

以前一直没写过可持久化线段树的区间覆盖，这里记一下

这题只用单点查询，我们在修改时把对应的区间打上标记并将其儿子设为空，那么单点查询时答案就是访问到的最深的存在的节点

维护区间和也是可以的，直接pushdown，只不过只用对存在的儿子pushdown，在pushup时不存在的儿子的值就是当前节点的标记了

#include
     
      #include
      
       using namespace std;char c[20000010];int ns;#define NUM(x) ('0'<=x&&x<='9')int rd(){	while(!NUM(c[ns]))ns++;	int x=0;	while(NUM(c[ns]))x=x*10+c[ns++]-'0';	return x;}int n;struct pseg{	struct seg{		int l,r,v;	}t[40000010];	int rt[5000010],M;	void modify(int pr,int&nr,int L,int R,int v,int l,int r){		t[nr=++M]=t[pr];		if(L<=l&&r<=R){			t[nr].v=v;			t[nr].l=t[nr].r=0;			return;		}		int mid=(l+r)>>1;		if(L<=mid)modify(t[pr].l,t[nr].l,L,R,v,l,mid);		if(mid
       
        >1,res;		if(p<=mid)			res=query(p,l,mid,t[x].l);		else			res=query(p,mid+1,r,t[x].r);		return~res?res:t[x].v;	}	void modify(int t,int l,int r,int v){		modify(rt[t],rt[t],l,r,v,1,n);	}	int query(int t,int p){		return query(p,1,n,rt[t]);	}}top,in;int s[2000010],t[2000010];void gao(int x,int len,int v){	t[x]=v;	s[x]=len*v;}void pushdown(int x,int ln,int rn){	if(t[x]){		gao(x<<1,ln,t[x]);		gao(x<<1|1,rn,t[x]);		t[x]=0;	}}void pushup(int x){s[x]=s[x<<1]+s[x<<1|1];}void modify(int L,int R,int v,int l,int r,int x){	if(L<=l&&r<=R)return gao(x,r-l+1,v);	int mid=(l+r)>>1;	pushdown(x,mid-l+1,r-mid);	if(L<=mid)modify(L,R,v,l,mid,x<<1);	if(mid
        
         <<1|1);	pushup(x);}int query(int L,int R,int l,int r,int x){	if(L<=l&&r<=R)return s[x];	int mid=(l+r)>>1,s=0;	pushdown(x,mid-l+1,r-mid);	if(L<=mid)s+=query(L,R,l,mid,x<<1);	if(mid
         
          <<1|1);	return s;}int main(){	fread(c,1,20000010,stdin);	in.t[0].v=-1;	top.t[0].v=-1;	int m,on,las,op,i,l,r,x,v;	n=rd();	m=rd();	on=rd();	las=0;	for(i=1;i<=m;i++){		top.rt[i]=top.rt[i-1];		in.rt[i]=in.rt[i-1];		op=rd();		if(op==1){			l=(rd()+on*las)%n+1;			r=(rd()+on*las)%n+1;			if(l>r)swap(l,r);			las=query(l,r,1,n,1);			printf("%d\n",las);		}		if(op==2){			l=(rd()+on*las)%n+1;			x=in.query(i,l);			if(x>0){				v=in.query(x-1,l);				if(v==-1)v=0;				in.modify(i,l,l,v);				v=top.query(x-1,l);				if(v==-1)v=0;				modify(l,l,v,1,n,1);				top.modify(i,l,l,v);			}		}		if(op==3){			l=(rd()+on*las)%n+1;			r=(rd()+on*las)%n+1;			x=rd();			if(l>r)swap(l,r);			modify(l,r,x,1,n,1);			top.modify(i,l,r,x);			in.modify(i,l,r,i);		}	}}