题意:n个数, m个操作
1. C l r d 给[l, r]区间的每个数加上d
2. Q l r: 查询[l, r]区间的和
3. H l r t: 查询第t个操作时[l, r]区间的和
4. B t: 回到第t个操作之后
因为有查询历史的区间和,故用主席树(保留了历史)
区间更新直接更新到每个子节点即可
出题人的题解 神么链接都打不开
#define lson l, m
#define rson m+1, r const int N=1e5+;
const double eps=1e-;
int L[N<<], R[N<<], sum[N<<];
LL ans[N<<];
int tot;
int a[N], T[N], Hash[N]; void pushup(int rt)
{
ans[rt]=ans[L[rt]]+ans[R[rt]];
} int build(int l, int r)
{
int rt=(++tot);
sum[rt]=;
if(l==r)
{
scanf("%I64d", &ans[rt]);
L[rt]=R[rt]=;
return rt;
}
int m=(l+r)>>;
L[rt]=build(lson);
R[rt]=build(rson);
pushup(rt);
return rt;
} int update(int pre, int _L, int _R, int l, int r, LL x)
{
int rt=(++tot);
L[rt]=L[pre], R[rt]=R[pre], sum[rt]=sum[pre], ans[rt]=ans[pre]+x*(_R-_L+);
if(_L<=l && r<=_R)
{
sum[rt]+=x;
return rt;
}
int m=(l+r)>>;
if(_R<=m)
L[rt]=update(L[pre], _L, _R, lson, x);
else if(_L>m)
R[rt]=update(R[pre], _L, _R, rson, x);
else
{
L[rt]=update(L[rt], _L, m, lson, x);
R[rt]=update(R[rt], m+, _R, rson, x);
}
return rt;
} LL query(int rt, int _L, int _R, int l, int r)
{
LL cnt=sum[rt]*(LL)(_R-_L+);
if(_L<=l && r<=_R)
return ans[rt];
int m=(l+r)>>;
if(_R<=m)
cnt+=query(L[rt], _L, _R, lson);
else if(_L>m)
cnt+=query(R[rt], _L, _R, rson);
else
{
cnt+=query(L[rt], _L, m, lson);
cnt+=query(R[rt], m+, _R, rson);
}
return cnt;
} int main()
{
int n, m;
while(~scanf("%d%d", &n, &m))
{
tot=;
T[]=build(, n);
int time=;
while(m--)
{
char op[];
scanf("%s", op);
if(op[]=='Q')
{
int l, r;
scanf("%d%d", &l, &r);
printf("%I64d\n", query(T[time], l, r, , n));
}
else if(op[]=='C')
{
int l, r;
LL x;
scanf("%d%d%I64d", &l, &r, &x);
T[time+]=update(T[time++], l, r, , n, x);
}
else if(op[]=='H')
{
int l, r, rt;
scanf("%d%d%d", &l, &r, &rt);
printf("%I64d\n", query(T[rt], l, r, , n));
}
else
scanf("%d", &time);
}
}
return ;
}
HDOJ 4348