自动搬运

查看原文

来自洛谷，原作者为

	ax_by_c ZJOI

搬运于2025-08-24 22:37:53，当前版本为作者最后更新于2023-07-24 22:36:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到这道题目，相信很多同学以为这题是主席树。

但是，就算用了主席树，还是会被卡空间。

其实，这题的正解就是线段树，只要一点点骚操作就好了。

首先，非常明显，前三个操作就是常规的线段树 2 的操作。

仔细观察第 4 个操作，可以发现不是回溯到任意时间，而是回溯到上一个 4 操作前。

所以，我们只要记录上一次 4 操作前的数组状态，就能够实现回溯操作。

那么一棵线段树怎么记录呢？

一棵不够就开两棵，其中一棵是记忆树，另一棵就是当前状态的树（当前树）。

前 3 个操作仍然用当前树完成。

而遇到 4 操作时，把这两棵树换一下（回溯），然后倒序处理操作。

并且，此时的记忆树正是这次 4 操作前的树。

时间复杂度证明：每个操作至多执行 2 次（正序和倒序各一次），所以复杂度不变。

code:

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=19260817;
const int N=5e5+5;
const int M=1e5+5;
int a[N];
struct node
{
	int sum,add,mul;
};
int mti(int a,int b)
{
	return (ll(a)%mod)*(ll(b)%mod)%mod;
}
int ad(int a,int b)
{
	return ll(a+b)%mod;
}
int lens(int l,int r)
{
	return r-l+1;
}
struct ST
{
	node tr[4*N];
	void pushup(int u,int l,int r)
	{
		tr[u].sum=ad(tr[u<<1].sum,tr[u<<1|1].sum);
	}
	void pushdown(int u,int l,int r)
	{
		int mid=l+((r-l)>>1);
		if(tr[u].mul!=1)
		{
			tr[u<<1].add=mti(tr[u<<1].add,tr[u].mul);
			tr[u<<1].mul=mti(tr[u<<1].mul,tr[u].mul);
			tr[u<<1].sum=mti(tr[u<<1].sum,tr[u].mul);
			tr[u<<1|1].add=mti(tr[u<<1|1].add,tr[u].mul);
			tr[u<<1|1].mul=mti(tr[u<<1|1].mul,tr[u].mul);
			tr[u<<1|1].sum=mti(tr[u<<1|1].sum,tr[u].mul);
			tr[u].mul=1;
		}
		if(tr[u].add)
		{
			tr[u<<1].add=ad(tr[u<<1].add,tr[u].add);
			tr[u<<1].sum=ad(tr[u<<1].sum,mti(lens(l,mid),tr[u].add));
			tr[u<<1|1].add=ad(tr[u<<1|1].add,tr[u].add);
			tr[u<<1|1].sum=ad(tr[u<<1|1].sum,mti(lens(mid+1,r),tr[u].add));
			tr[u].add=0;
		}
	}
	void build(int u,int l,int r)
	{
		tr[u].mul=1;
		if(l==r)
		{
			tr[u].sum=a[l];
			return ;
		}
		int mid=l+((r-l)>>1);
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u,l,r);
	}
	void update_add(int u,int l,int r,int ql,int qr,int vu)
	{
		if(ql<=l&&r<=qr)
		{
			tr[u].add=ad(tr[u].add,vu);
			tr[u].sum=ad(tr[u].sum,mti(vu,lens(l,r)));
			return ;
		}
		pushdown(u,l,r);
		int mid=l+((r-l)>>1);
		if(ql<=mid)
		{
			update_add(u<<1,l,mid,ql,qr,vu);
		}
		if(mid+1<=qr)
		{
			update_add(u<<1|1,mid+1,r,ql,qr,vu);
		}
		pushup(u,l,r);
	}
	void update_mul(int u,int l,int r,int ql,int qr,int vu)
	{
		if(ql<=l&&r<=qr)
		{
			tr[u].add=mti(tr[u].add,vu);
			tr[u].mul=mti(tr[u].mul,vu);
			tr[u].sum=mti(tr[u].sum,vu);
			return ;
		}
		pushdown(u,l,r);
		int mid=l+((r-l)>>1);
		if(ql<=mid)
		{
			update_mul(u<<1,l,mid,ql,qr,vu);
		}
		if(mid+1<=qr)
		{
			update_mul(u<<1|1,mid+1,r,ql,qr,vu);
		}
		pushup(u,l,r);
	}
	int Q(int u,int l,int r,int ql,int qr)
	{
		if(ql<=l&&r<=qr)
		{
			return tr[u].sum;
		}
		pushdown(u,l,r);
		int mid=l+((r-l)>>1);
		int ans=0;
		if(ql<=mid)
		{
			ans=ad(ans,Q(u<<1,l,mid,ql,qr));
		}
		if(mid+1<=qr)
		{
			ans=ad(ans,Q(u<<1|1,mid+1,r,ql,qr));
		}
		return ans;
	}
};
ST tr[2];
int n,m;
int op[M],l[M],r[M],x[M];
int cur;
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	tr[0].build(1,1,n);
	tr[1].build(1,1,n);
	cur=1;
	int lst=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&op[i]);
		if(op[i]==1)
		{
			scanf("%d %d %d",&l[i],&r[i],&x[i]);
		}
		if(op[i]==2)
		{
			scanf("%d %d %d",&l[i],&r[i],&x[i]);
		}
		if(op[i]==3)
		{
			scanf("%d %d",&l[i],&r[i]);
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(op[i]==1)//常规操作
		{
			tr[cur].update_add(1,1,n,l[i],r[i],x[i]);
		}
		if(op[i]==2)
		{
			tr[cur].update_mul(1,1,n,l[i],r[i],x[i]);
		}
		if(op[i]==3)
		{
			printf("%d\n",tr[cur].Q(1,1,n,l[i],r[i]));
		}
		if(op[i]==4)
		{
			for(int j=i-1;j>lst;j--)//倒着处理
			{
				if(op[j]==1)
				{
					tr[1-cur].update_add(1,1,n,l[j],r[j],x[j]);
				}
				if(op[j]==2)
				{
					tr[1-cur].update_mul(1,1,n,l[j],r[j],x[j]);
				}
			}
			cur=1-cur;//互换树
			lst=i;
		}
	}
	return 0;
}

坑点：

1.不要存 l 和 r，不然会 MLE 。

2.别用 long long，强制转换就行了。

3.倒着处理时 3 操作不用做。

4.两棵树一开始都是初始状态。

5.不用管题目里说的 45M，只要尽你所能压就好了。