标记不下传线段树（混蛋树）

开坑开坑 KL ZXR都写了不能懒了

*************************************

万年大坑

*************************************

ZXR是大神犇

*************************************

我当然是抄了一份

*************************************

标记不下船线段树（sign not leave the boat)

把线段树的一个lazy标记变成两个来避免pushdown

s:表示当前增量cover当前节点

f:表示当前增量belongto当前节点

因此

更新是更新链上的所有f（去搅基）和终点节点的s

查询时累加链上的s（去搅基）和终点节点的f

*************************************

ZXR真是吊

*************************************

处理更改标记:

好像只能转化成增量。。。。。我不知道

YMZXR

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 #define lson l, m, idx << 1
 5 #define rson m + 1, r, idx << 1 | 1
 6 const int N = 101000;
 7 typedef long long LL;
 8 LL sum[N], f[N << 1], s[N << 2], ans;
 9 int n, q, a[N]; 
10 //s : cover
11 //f : belong
12 inline void updata (int c, int L, int R, int l, int r, int idx)
13 {
14     if (L <= l && r <= R)
15     {
16         s[idx] += c;
17         return ;
18     }
19     f[idx] += c * (min (R, r) - max (L, l) + 1);
20     int m = l + r >> 1;
21     if (L <= m) updata (c, L, R, lson);
22     if (R > m) updata (c, L, R, rson);
23 }
24 inline void query (int L, int R, int l, int r, int idx)
25 {
26     ans += s[idx] * (min (R, r) - max (L, l) + 1);
27     if (L <= l && r <= R)
28     {
29         ans += f[idx];
30         return ;
31     }
32     
33     int m = l + r >> 1;
34     if (L <= m) query (L, R, lson);
35     if (R > m) query (L, R, rson);
36 }
37 int main ()
38 {
39     scanf ("%d%d", &n, &q);
40     for (int i = 1; i <= n; i ++)
41         scanf ("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
42     char s[10];
43     long long c;
44     for (int i = 1, a, b; i <= q; i ++)
45     {
46         scanf ("%s", s);
47         if (s[0] == 'Q')
48             scanf ("%d%d", &a, &b), ans = 0, query (a, b, 1, n, 1), printf ("%lld\n", sum[b] - sum[a - 1] + ans);
49         if (s[0] == 'C')
50             scanf ("%d%d%lld", &a, &b, &c), updata (c, a, b, 1, n, 1);
51     }
52     return 0;
53 }