[HDU4348]To the moon（主席树）

传送门

对于这个题，显然要打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

上一篇：[HNOI2009]梦幻布丁（链表+启发式合并）

下一篇：对于2-sat问题的求解

---

主席树