可持久化线段树求调

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],w[N<<5],lch[N<<5],rch[N<<5],lzy[N<<5],gen[N],preNode,Nodeid;
struct Node
{
	int t,x,k;
}b[N+5];
int WYXGJD(int &p)
{
	if(p>preNode)
	{
		return p;
	}
	else
	{
		w[++Nodeid]=w[p];
		lch[Nodeid]=lch[p];
		rch[Nodeid]=rch[p];
		p=Nodeid;
		return p;
	}
}
void pushup(int u)
{
	if(u==0)return ;
	w[u]=max(w[lch[u]],w[rch[u]]);
	return ;
}
int build(int l,int r)
{
	int u=++Nodeid;
	//cout<<u<<" "<<l<<" "<<r<<endl;
	if(l==r)
	{
		w[u]=a[l];
		return u;
	}
	int mid=(l+r)/2;
	lch[u]=build(l,mid);
	rch[u]=build(mid+1,r);
	pushup(u);
	return u;
}
void updata(int &u,int l,int r,int ql,int qr,int x)
{
	//cout<<ql<<" "<<qr<<endl;
	if(ql<=l&&r<=qr)
	{
		WYXGJD(u);
		w[u]=x;
		//lzy[u]+=x;
		return ;
	}
	int mid=(l+r)/2;
	if(r<ql||qr<l)return ;
	WYXGJD(u);
	if(l<=mid)
	{
		updata(lch[u],l,mid,ql,qr,x);
	}
	if(r>=mid+1)
	{
		updata(rch[u],mid+1,r,ql,qr,x);
	}
	pushup(u);
}
int Q(int u,int l,int r,int ql,int qr)
{
	//cout<<u<<" "<<l<<" "<<r<<endl;
	if(ql<=l&&r<=qr)
	{
		//cout<<u<<"*"<<w[u]<<endl;
		return w[u];
	}
	int mid=(l+r)/2;
	int maxx=0;
	if(r<ql||qr<l)return 0;
	if(l<=mid)
	{
		maxx=Q(lch[u],l,mid,ql,qr);
	}
	if(r>=mid+1)
	{
		maxx=max(maxx,Q(rch[u],mid+1,r,ql,qr));
	}
	return maxx+lzy[u];
}
bool cmp(Node x,Node y)
{
	return x.t<y.t;
}
bool cmpp(Node x,int y)
{
	return x.t<=y;
}
int main()
{
	int n,m,T;
	cin>>n>>m>>T;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n);
	for(int i=1;i<=m;i++)
	{
		cin>>b[i].t>>b[i].x>>b[i].k;
	}
	sort(b+1,b+m+1,cmp);
	
	gen[0]=1;
	for(int i=1;i<=m;i++)
	{
		if(b[i].t!=b[i-1].t)preNode=Nodeid,gen[b[i].t]=gen[b[i-1].t];
		updata(gen[b[i].t],1,n,b[i].x,b[i].x,b[i].k);
		
	}
	/*
	for(int i=1;i<=n;i++)
	{
		cout<<gen[i]<<" ";
	}
	*/
	//cout<<endl;
	int las=0;
	for(int i=1;i<=m;i++)
	{
		int l,r,bb,c;
		cin>>l>>r>>bb>>c;
		int t=(bb*las+c)%T;
		if(t<0)t=0; 
		if(gen[t]==0)gen[t]=gen[b[lower_bound(b+1,b+m+1,t,cmpp)-b].t];

		las=Q(gen[t],1,n,l,r);
		//cout<<t<<endl;
		//dfs(gen[t],1,n);
		//cout<<endl;
		cout<<las<<endl;
	}
	return 0;
}
```cpp