HDU-4348 to the moon(可持久化线段树) 解题报告
xzc 2019/4/12
题意:
- 维护区间和
- 一开始给出数列a[n]的初值,时间戳t为0
- C L R add 更新操作,把数列[L,R]这部分都加上add,并且时间戳t++
- Q L R 询问操作,询问当前时间下数列区间[L,R]的和
- H L R h 询问操作,询问过去某个时间h(h<t)的区间和[L,R]
- B tt 时间点回到过去的tt(tt<t)
样例:
Sample input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
2 4
0 0
C 1 1 1
C 2 2 -1
Q 1 2
H 1 2 1
Sample output
4
55
9
15
0
1
分析:
可持久化线段树
每次更新(C操作)的时候,时间戳t++,新建一棵线段树,并记录线段树根节点的在内存池中的编号为root[t]
询问H时,在root[H]的那棵线段树中查询
询问当前区间时,在root[t]的线段树中查询
B操作时,直接把t该为tt,然后cnt=root[tt+1]这样省空间,相当于是delete了后面的所有树(我觉得这一点我写得非常好~)
int build(left,right)函数用于建立第一棵t=0时的树,返回值为该节点从内存池中分配的下标
update(left,right,x,y,add,&t,p)函数用引用的方式实现了返回新分配节点的下标,这个几点表示的区间为[left,right],要更新的范围是[x,y],都+add, t用于返回下标,p是先前时间戳为t-1时候的线段树根节点的下标
采用永久化标记的思想,lazy不push_down;不论是更新还是查询,当前节点代表的区间[left,right]一定包含了要查询或者更新的范围[x,y]。
- 在更新中,进入函数的节点都是包含了更新范围的,都是要新建的节点,如果两个范围下好重合,那么直接lazy+=add;return;不必再往下新建子节点了
- 在查询中,进入函数的节点区间一定也是包含了查询范围的,如果恰好重合,那么return sum[t];不然,就分类讨论要查询区间是在左子树,还是右子树,还是跨了mid。
- 这个[left,righy]一定包含[x,y]的性质使得我们可以直接求出lazy*(y-x+1)
- (发现不写结构体代码量少了很多)
程序还是跑得飞快的,空间也不多
代码:
/* Status: Accepted Time: 218ms Memory: 10816kB Length: 2608 Lang: G++ Submitted: 2019-04-11 21:40:54 */
#include <bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
#define MP make_pair
#define pb push_back
using namespace std;
const int maxn = 1e5+4;
const int N = maxn*20;
int a[maxn];
int lson[N],rson[N],root[N],n,cnt;
LL sum[N],lazy[N];
int build(int left,int right)
{
int t = ++cnt;
lazy[t] = 0;
if(left==right)
{
sum[t] = a[left];
return t;
}
int mid = (left+right)>>1;
lson[t] = build(left,mid);
rson[t] = build(mid+1,right);
sum[t] = sum[lson[t]]+sum[rson[t]];
return t;
}
void update(int left,int right,int x,int y,int add,int &t,int p)
{
t = ++cnt; ///该区间[left,right]一定包含要更新的区间[x,y]
lazy[t] = lazy[p];
lson[t] = lson[p];
rson[t] = rson[p];
sum[t] = sum[p]+1ll*(y-x+1)*add;
if(left==x&&right==y)
{
lazy[t] += add;
return;
}
int mid = (left+right)>>1;
if(y<=mid) update(left,mid,x,y,add,lson[t],lson[p]);
else if(x>mid) update(mid+1,right,x,y,add,rson[t],rson[p]);
else
update(left,mid,x,mid,add,lson[t],lson[p]),
update(mid+1,right,mid+1,y,add,rson[t],rson[p]);
}
LL query(int left,int right,int qx,int qy,int t)
{
if(left==qx&&right==qy) return sum[t];
LL add = lazy[t]*(qy-qx+1);
int mid = (left+right)>>1;
if(qy<=mid) return query(left,mid,qx,qy,lson[t])+add;
else if(qx>mid) return query(mid+1,right,qx,qy,rson[t])+add;
else return
query(left,mid,qx,mid,lson[t])+
query(mid+1,right,mid+1,qy,rson[t])+add;
}
int main()
{
int m,t,tt,h,l,r,add,ca=0;
char op[3];
while(scanf("%d%d",&n,&m)!=EOF)
{
For(i,1,n) scanf("%d",a+i);
cnt = -1;
root[0] = build(1,n);
if(ca++) printf("\n");
t = 0; ///current time
while(m--)
{
scanf("%s",op);
switch (op[0])
{
case 'Q':
scanf("%d%d",&l,&r);
printf("%lld\n",query(1,n,l,r,root[t]));
break;
case 'B':
scanf("%d",&t);cnt = root[t+1]-1;
break;
case 'H':
scanf("%d%d%d",&l,&r,&tt);
printf("%lld\n",query(1,n,l,r,root[tt]));
break;
case 'C':scanf("%d%d%d",&l,&r,&add);
++t;
update(1,n,l,r,add,root[t],root[t-1]);
break;
}
}
}
return 0;
}