p8310
看到这道题目，相信很多同学以为这题是主席树。
但是，就算用了主席树，还是会被卡空间。
其实，这题的正解就是线段树，只要一点点骚操作就好了。
首先，非常明显，前三个操作就是常规的线段树 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，只要尽你所能压就好了。