)
此题可以作为可持久化线段树区间修改的模板题于罗勇军老师的《算法竞赛上册》4.4 可持久化线段树的区间更新部分被简单提及了一嘴 —— 说是按标准主席树编码即可然而并没有给出具体做法可能是不想限制大家的想法吧。但实际上也并不是直接按照标准主席树编码那么简单这种需要可持久化的区间操作引入了一个新的操作 —— 标记永久化话不多说直接进入主题。题解简化题意给定一个长度为的序列以及个操作操作有如下四种给内的每个数加上并将时间加。查询当前内所有数的和。查询时内所有数的和。返回时间。其中当前时间初始为只有操作才会使增加如果选择返回时间则之后的操作全部作废。思路当读到查询历史时间的区间和时会发现这题需要可持久化并且就是每个树根的编号。那么考虑如何实现区间修改。首先区间操作为了防止爆时间懒标记肯定时需要的。但如果像普通线段树一样每次访问到一个结点就下传标记那么会使得历史结点的值被改变。怎么办呢方法一容易想到的一种方案是每次下传的时候创建两个子结点继承上一个版本的信息后再下传懒标记。显然这一方案十分的正确然而这题仅给了 64M 的空间把这个单次操作产生的空间约为的方案 pass 掉了。所以得考虑另一种方法就是 标记永久化。方法二 - 标记永久化什么是标记永久化就是字面意思将懒标记打完以后就放在那个结点再也不动了会被新版本继承但不会再被下传这样就避免了更改历史结点的问题。然后就是如何利用标记永久化求和这样想如果直接询问根节点那么子结点的标记肯定没法计算所以上传操作 (即 updata) 仍然需要如果有一个结点存在标记那么它的整棵子树都要增加数值若询问的区间在它子树内而标记又不能下传难以直接计算所以开一个变量 Sum_Tag 来记录经过该结点时增量通过 Sum_Tag 统计从根一路到达目标区间的增量。如此一来单次操作产生的空间约为在满足空间需求的条件下实现了区间修改和查询。代码思路讲完了更具体的细节见代码#include#includeusing namespace std;typedef long long ll;const int N1e55;int n,m,T;ll a[N];int tid,rt[N];struct Tree{int ls,rs,tag;ll sum;Tree() {lsrssumtag0;}}tr[N*25];#define mid ((lr)1)void updata(int p,int l,int r){int lstr[p].ls;int rstr[p].rs;tr[p].sumtr[ls].sumtr[rs].sum(r-l1)*tr[p].tag;//加上自身区间的增量}void build(int p,int l,int r){ptid;if(lr){tr[p].suma[l];return ;}build(tr[p].ls,l,mid);build(tr[p].rs,mid1,r);updata(p,l,r);}void modify(int lp,int p,int l,int r,int x,int y,ll v){ptid;tr[p]tr[lp];if(xlry){tr[p].tagv;tr[p].sum(r-l1)v;return ;}if(xmid) modify(tr[lp].ls,tr[p].ls,l,mid,x,y,v);if(midy) modify(tr[lp].rs,tr[p].rs,mid1,r,x,y,v);updata(p,l,r);}ll query(int p,int l,int r,int x,int y,ll Sum_Tag){//通过Sum_Tag累计从根到目标区间的所有增量if(xlry) return tr[p].sumSum_Tag(r-l1);//添加累计增量ll ans0;//进入子区间时才给Sum_Tag增加自身的tagif(xmid) ansquery(tr[p].ls,l,mid,x,y,Sum_Tagtr[p].tag);if(midy) ansquery(tr[p].rs,mid1,r,x,y,Sum_Tagtr[p].tag);return ans;}#undef midint main(){while(scanf(“%d%d”,n,m)!EOF){for(int i1;in;i){scanf(“%lld”,a[i]);}Ttid0;build(rt[T],1,n);char op;int l,r,d,t;for(int i1;im;i){cinop;if(op’C’){scanf(“%d%d%d”,l,r,d);modify(rt[T],rt[T1],1,n,l,r,d);T;}else if(op‘Q’){scanf(“%d%d”,l,r);printf(“%lld\n”,query(rt[T],1,n,l,r,0));}else if(op‘H’){scanf(“%d%d%d”,l,r,t);printf(“%lld\n”,query(rt[t],1,n,l,r,0));}else if(op‘B’){scanf(“%d”,t);Tt;}}}return 0;
