AC的故事大结局悲剧版（下）
事情进展得很顺利，测试修正后的ACRobot所向披靡，挂起不到一天，便从互联网的茫茫大海中搜寻到了小C的踪迹，小C被关押在神秘组织的大本营，于是小A便赶紧展开营救行动。
小A发现，神秘组织在基地外围布置了n 个营地，编号从1 - n，每个营地都有大量的兵力，小A完全无法进入，不过在潜伏一周以后小A发现每个营地的士兵数量天天都在变动，所以小A决定写个软件来统计敌方兵力情况。
程序具体如下：
在t=0天时每个营地有Ai名士兵。
现有m个操作，分三类：
A：l 到r 营地在新的一天里新增士兵k名（随后时间从t 现在变成t+1了）
B：问第i天 l 到r 营地共有士兵几名。
C：时间倒流到x天 。（厉害了。。。）
小A只负责深入重围，抱得美人归和撒狗粮，于是就把这个计算的任务就交给了在座的各位。
（1号结局，本场有人AC了这题：经过计算终于得出结论，发现营地真是守卫森严，根本没有办法攻入，小A冒死进去救人，被乱刀砍死，小C见状也从敌人大本营100楼跳下。后来有人说当时看到两只蝴蝶，一只从大本营楼上飞下来，一只从地上飞上去。）
（2号结局，本场没有人AC这题：五个小时过去了，小C长时间在绝望中度过，于是便动了轻生的念头，终于她找个一个合适的时机，一头撞向石柱，那一刻，小A也心有所感，拿出深藏许久的宝刀引颈自戮，那一霎那，天空突然阴云密布，不一会被下起了倾盆大雨。后来有人说当时看到了两只蝴蝶颤颤巍巍地飞到了一起，又一起飞走了。）
虽然小A没有救出小C，但江湖中人感叹小A和小C的感情，为他们起了个名字AC自动机，用来祭奠他们，而小A当初写的爬虫ACRobot无休无止地爬在互联网上，苦寻自家主人却无果。
有多组样例，每组样例首先是一个n 表示营地数量。 1<=n<=10万
接下来n 个整数表示每个营地的初始人数。
接下来一个m 表示操作数目。1<=m<=10万
接下来分A、B、C三类操作，格式如下：
A l r k，1<=l<=r<=n, k为整数
B t l r，0<=t<=当前时间， 1<=l<=r<=n
C x，0<=x<=当前时间
题目中的整数范围是[-2^23, 2^23-1]
每组测试样例首先输出样例编号。
对于B 操作，给出人数。
参见样例。
3 1 2 3 3 B 0 1 3 A 1 2 2 B 1 1 3 3 1 2 3 3 B 0 1 3 A 1 2 2 B 0 1 3
Case 1: 6 10 Case 2: 6 6
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题，请不要查看标签
如果您已经通过了该题，请务为该题贴上标签
假设更新（1，3）那么先给（1，4）.sum+= val * （4 - 1 + 1），
然后向下遍历，给（1，2）打上标记，然后lazy不下压，这个时候（1，2）.sum += val *(2 - 1 + 1)
给（1，2）.lazy += val;假设我要查询的是（1，1）那么我们在遍历的时候，声明一个变量sums，来存储需要
更新的lazy值，因为上一次我们更新停止在了（1，2），然后我们遍历到（1，2）的时候sums += （1，2).lazy
然后往下查询，查询到了我们想要的（1，1），那么就（1，1）.sum += sums * （1 - 1 + 1）；
这样就可以给出答案了
贴上代码：
（代码有注释）
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1e5 + 5; typedef long long ll; typedef struct SEGTREE { ll l, r, ls, rs, sum, lazy; }segtree; segtree seg[MAXN * 20]; ll arr[MAXN]; ll root[MAXN]; ll tot = 0; ll build(ll now, ll l, ll r) { ll p = ++ tot; seg[p].lazy = 0; seg[p].sum = 0; seg[p].ls = l; seg[p].rs = r; if(l == r) { seg[p].sum = arr[l]; return p; } ll mid = (l + r) >> 1; seg[p].l = build(seg[p].l, l, mid); seg[p].r = build(seg[p].r, mid + 1, r); seg[p].sum = seg[seg[p].l].sum + seg[seg[p].r].sum; return p; } ll update(ll l, ll r, ll now, ll val) { ll p = ++ tot; seg[p] = seg[now]; seg[p].sum += (r - l + 1) * val; ///更新包含了update范围的节点 if(seg[p].ls == l && seg[p].rs == r) { seg[p].lazy += val; ///[l,r]如果是匹配的话，那么更新lazy的值 ///不往下更新，这样的话标记永久化后，就可以节省空间 ///不用更新一次就多出一颗线段树 ///这样的话，在下次查询的时候，查询范围小于最后这个节点的范围 ///只要记录lazy值然后向下查询到底，进行更新就正确了 return p; } ll mid = (seg[p].ls + seg[p].rs) / 2; if(r <= mid) { seg[p].l = update(l, r, seg[p].l, val); } else if(mid < l) { seg[p].r = update(l, r, seg[p].r, val); } else { seg[p].l = update(l, mid, seg[p].l, val); seg[p].r = update(mid + 1, r, seg[p].r, val); } return p; } ll query(ll now, ll l, ll r, ll lazy) ///lazy 是记载我要查询的这个区间是如何变化的， ///因为lazy只标记在要更新的区间，lazy是不下压的 ///那么我每次查询的时候只要把lazy经过的区间的lazy进行记载 ///然后向下累计，直到要查询的区间，在添加上去，就完成了标记永久化 ///或许你会不理解为什么是这样操作的 ///因为在前面我们进行update的时候，把对应的[l,r]更新了，但是比[l,r]更小的范围是没有 ///进行更新的，那么我们只要记录从父节点向下更新到我们要查询的节点，所增加的lazy的值 ///就可以得到查询区间更新的值，即lazy * (r - l + 1) ///或许你会说，我们不是更新到前面操作的更新区间的[l,r]，就会改变lazy值吗？那么再加为什么不会 ///发生错误，其实很简单，更新区间的[l,r]不向下更新，我们如果查询的依旧是[l,r]，那么到了l,r就结束了 ///是不会再向下的，所以是没有影响的 { ll p = now; if(seg[p].ls == l && seg[p].rs == r) { return seg[p].sum + lazy * (r - l + 1); } ll mid = (seg[p].ls + seg[p].rs) / 2; if(r <= mid) { return query(seg[p].l, l, r, lazy + seg[p].lazy); } else if(l > mid) { return query(seg[p].r, l, r, lazy + seg[p].lazy); } else { return query(seg[p].l, l, mid, lazy + seg[p].lazy) + query(seg[p].r, mid + 1, r, lazy + seg[p].lazy); } } void change(ll ans) ///这里有个坑点，即如果ans == day，那么root[ans + 1] = 0, 0 - 1 = - 1 ///那么就re了，emmmmm ///所以特判下==day就ok了 { tot = root[ans + 1] - 1; } int main() { int n, m, flag; flag = 0; while(~scanf("%d",&n)) { tot = 0; for (int i = 1; i <= n; i ++) { scanf("%lld",&arr[i]); } root[0] = build(tot, 1, n); printf("Case %d: ",++ flag); ll day = 0; scanf("%d",&m); for (int i = 0; i < m; i ++) { char temp; cin >> temp; if(temp == 'A') { ll l, r, val; scanf("%lld%lld%lld", &l, &r, &val); root[day + 1] = update(l, r, root[day], val); day ++; } else if(temp == 'B') { ll l, r, t; scanf("%lld%lld%lld", &t, &l, &r); ll re = query(root[t], l, r, 0); printf("%lld ",re); } else { ll ans; scanf("%lld",&ans); if(ans < day) change(ans); day = ans; } } } return 0; }