[HDU4417]Super Mario（主席树+离散化）

传送门

又是一道主席树模板题，注意数组从0开始，还有主席树耗费空间很大，数组开大点，之前开小了莫名其妙TLE。QAQ

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ls son[now][0], l, mid 5 #define rs son[now][1], mid + 1, r 6 7 using namespace std; 8 9 const int N = 100005; 10 11 int T, n, m, sz, tot, ans; 12 int a[N], b[N], rt[N], son[10 * N][2], sum[10 * N]; 13 14 inline void build(int &now, int l, int r) 15 23 24 inline void update(int &now, int l, int r, int last, int x) 25 35 36 inline void query(int s, int t, int l, int r, int x) 37 43 int mid = (l + r) >> 1; 44 if(x <= mid) query(son[s][0], son[t][0], l, mid, x); 45 else 46 50 } 51 52 inline void clear() 53 61 62 int main() 79 printf("Case %d:\n", ++j); 80 for(i = 1; i <= m; i++) 81 90 else printf("0\n"); 91 } 92 } 93 return 0; 94 }
View Code

上一篇：【模板】Treap

下一篇：双连通分量

---

主席树 离散化