传送门
对于这个题，显然要打lazy标记了，但是lazy标记pushdown的时候肯定会增加一大堆节点，然后就MLE了。（题解这么说的，我其实不会pushdown）
所以，就换另一种方式，把标记直接打到当前区间，把当前区间的父亲节点大小都更新。求区间和的时候把沿途的标记都加起来就可以了。
注意分多钟情况。
——代码
1 #include <cstdio> 2 #define ls son[now][0], l, mid 3 #define rs son[now][1], mid + 1, r 4 #define LL long long 5 6 using namespace std; 7 8 const int N = 5000005; 9 10 int n, m, tot; 11 int rt[N], son[N][2], add[N]; 12 LL sum[N]; 13 14 inline void pushup(int now) 15 18 19 inline void build(int &now, int l, int r) 20 28 int mid = (l + r) >> 1; 29 build(ls); 30 build(rs); 31 pushup(now); 32 } 33 34 inline void update(int &now, int l, int r, int last, int ql, int qr, int x) 35 47 int mid = (l + r) >> 1; 48 if(qr <= mid) update(ls, son[now][0], ql, qr, x); 49 else if(ql > mid) update(rs, son[now][1], ql, qr, x); 50 else 51 55 } 56 57 inline LL query(int now, int l, int r, int ql, int qr) 58 66 67 int main() 68 88 } 89 } 90 return 0; 91 }View Code
上一篇：[luoguP1352] 没有上司的舞会（DP）
下一篇：[luoguP1186] 玛丽卡（spfa）
主席树
