[关闭]
@ljt12138 2017-05-28T18:17:56.000000Z 字数 13025 阅读 823

数据结构训练

可并堆

学习了一个斜堆的写法，非常好写，于是又去切了可并堆模板[Apio2012]dispatching：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  6. struct lheap {
  7.     long long dat;
  8.     int lc, rc;
  9.     lheap() { lc = rc = 0; }
  10. } tree[MAXN*2];
  11. int tp = 0;
  13. int merge(int a, int b)
  14. {
  15.     if (a == 0 || b == 0) return a+b;
  16.     if (tree[a].dat < tree[b].dat) swap(a, b);
  17.     swap(tree[a].lc, tree[a].rc);
  18.     return tree[a].rc = merge(tree[a].rc, b), a;
  19. }
  21. long long pop(int &a)
  22. {
  23.     long long ret = tree[a].dat;
  24.     a = merge(tree[a].lc, tree[a].rc);
  25.     return ret;
  26. }
  28. struct node {
  29.     int to, next;
  30. } edge[MAXN];
  31. int head[MAXN], top = 0;
  32. inline void push(int i, int j)
  33. { edge[++top] = (node){j, head[i]}, head[i] = top; }
  35. int n;
  36. long long m, ans = 0;
  37. int b[MAXN];
  38. long long c[MAXN], l[MAXN];
  39. int rt;
  41. int dfs(int nd, long long &sig, int &cnt)
  42. {
  43.     int tr = ++tp;
  44.     long long sum; int ct;
  45.     sig = tree[tr].dat = c[nd], cnt = 1;
  46.     for (int i = head[nd]; i; i = edge[i].next)
  47.         tr = merge(tr, dfs(edge[i].to, sum, ct)), sig += sum, cnt += ct;
  48.     while (sig > m) sig -= pop(tr), cnt--;
  49.     ans = max(ans, cnt*l[nd]);
  50.     return tr;
  51. }
  53. int main()
  54. {
  55.     scanf("%d%lld", &n, &m);
  56.     for (int i = 1; i <= n; i++) {
  57.         scanf("%d%lld%lld", &b[i], &c[i], &l[i]);
  58.         if (b[i]) push(b[i], i);
  59.         else rt = i;
  60.     }
  61.     long long t;
  62.     int cnt;
  63.     dfs(rt, t, cnt);
  64.     printf("%lld\n", ans);
  65.     return 0;
  66. }

bzoj1078: [SCOI2008]斜堆

结论题/找规律题，递归求解发现应该交替插入，然后只要分类讨论四种情况就好。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 105;
  6. int lc[MAXN], rc[MAXN], n;
  8. int solve(int nd, int a[], int &top)
  9. {
  10.     top = 0;
  11.     int l[MAXN], r[MAXN], ltop = 0, rtop = 0, lf = 0, rf = 0;
  12.     if (lc[nd] != -1) solve(lc[nd], l, ltop);
  13.     if (rc[nd] != -1) solve(rc[nd], r, rtop);
  14.     if (ltop-rtop > 1) {
  15.         while (ltop-lf > rtop-rf) a[++top] = l[++lf];
  16.         a[++top] = nd;
  17.         while (ltop-lf > 0) a[++top] = r[++rf], a[++top] = l[++lf];
  18.     } else if (ltop == rtop+1) {
  19.         a[++top] = nd;
  20.         while (ltop-lf > 0) {
  21.             a[++top] = l[++lf];
  22.             if (rtop-rf > 0) a[++top] = r[++rf];
  23.         }
  24.     } else if (ltop == rtop) {
  25.         a[++top] = nd;
  26.         while (rtop-rf > 0)
  27.             a[++top] = r[++rf], a[++top] = l[++lf];
  28.     } else {
  29.         while (rtop-rf > ltop-lf-1) a[++top] = r[++rf];
  30.         a[++top] = nd;
  31.         while (ltop-lf > 0) {
  32.             a[++top] = l[++lf];
  33.             if (rtop-rf > 0) a[++top] = r[++rf];
  34.         }
  35.     }
  36. }
  38. int main()
  39. {
  40.     int a[MAXN], u;
  41.     memset(lc, -1, sizeof lc);
  42.     memset(rc, -1, sizeof rc);
  43.     scanf("%d", &n);
  44.     for (int i = 1; i <= n; i++) {
  45.         scanf("%d", &u);
  46.         if (u < 100) lc[u] = i;
  47.         else rc[u-100] = i;
  48.     }
  49.     solve(0, a, u);
  50.     for (int i = 1; i <= u; i++)
  51.         printf("%d ", a[i]);
  52.     return 0;
  53. }

bzoj4003: [JLOI2015]城池攻占

比较有意思的数据结构题。大概就是用可并堆维护还存活着的骑士，然后只需要lazy_tag就好了。

注意两种lazy_tag一定要考虑彼此的影响！

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 300005;
  6. struct sheap {
  7.     pair<long long, int> dat;
  8.     int lc, rc;
  9.     long long tag1, tag2;
  10.     sheap() { tag1 = 0, tag2 = 1; }
  11. } tree[MAXN*2];
  13. int tp = 0;
  15. long long a[MAXN], b[MAXN];
  16. int n, m;
  17. long long h[MAXN];
  18. long long s[MAXN];
  19. int c[MAXN], u;
  20. vector<int> v[MAXN];
  22. inline void pdw(int nd)
  23. {
  24.     if (!nd) return; 
  25.     tree[nd].dat.first *= tree[nd].tag2;
  26.     if (tree[nd].lc)
  27.         tree[tree[nd].lc].tag2 *= tree[nd].tag2, tree[tree[nd].lc].tag1 *= tree[nd].tag2;
  28.     if (tree[nd].rc)
  29.         tree[tree[nd].rc].tag2 *= tree[nd].tag2, tree[tree[nd].rc].tag1 *= tree[nd].tag2;
  30.     tree[nd].dat.first += tree[nd].tag1;
  31.     if (tree[nd].lc) tree[tree[nd].lc].tag1 += tree[nd].tag1;
  32.     if (tree[nd].rc) tree[tree[nd].rc].tag1 += tree[nd].tag1;
  33.     tree[nd].tag1 = 0, tree[nd].tag2 = 1;
  34. }
  36. inline void mul_dt(int nd, long long dt)
  37. { if (!nd) return; tree[nd].tag2 *= dt, tree[nd].tag1 *= dt; }
  38. inline void plus_dt(int nd, long long dt)
  39. { if (!nd) return; tree[nd].tag1 += dt; }
  41. void tour(int nd, int tab = 0)
  42. {
  43.     if (!nd) return;
  44.     pdw(nd);
  45.     tour(tree[nd].lc, tab+2), tour(tree[nd].rc, tab+2);
  46. }
  47. int merge(int a, int b)
  48. {
  49.     if (a == b && a != 0) throw;
  50.     pdw(a), pdw(b);
  51.     if (a == 0 || b == 0) return a+b;
  52.     if (tree[a].dat.first > tree[b].dat.first) swap(a, b);
  53.     swap(tree[a].lc, tree[a].rc);
  54.     return tree[a].lc = merge(tree[a].lc, b), a;
  55. }
  57. inline long long top_ele(int a)
  58. { return pdw(a), tree[a].dat.first; }
  60. inline void pop(int &a)
  61. {
  62.     pdw(a);
  63.     a = merge(tree[a].lc, tree[a].rc);
  64. }
  66. struct node {
  67.     int to, next;
  68. } edge[MAXN];
  69. int head[MAXN], top = 0;
  70. inline void push(int i, int j)
  71. { edge[++top] = (node){j, head[i]}, head[i] = top; }
  73. int cnt[MAXN], depth[MAXN], death[MAXN];
  75. int dfs(int nd)
  76. {
  77.     int hp = 0;
  78.     for (int i = 0; i < v[nd].size(); i++) {
  79.         hp = merge(hp, (tree[++tp].dat = make_pair(s[v[nd][i]], v[nd][i]), tp));
  80.     }
  81.     for (int i = head[nd]; i; i = edge[i].next) {
  82.         depth[edge[i].to] = depth[nd]+1;
  83.         hp = merge(hp, dfs(edge[i].to));
  84.     }
  85.     while (hp && top_ele(hp) < h[nd]) {
  86.         pair<long long, int> dat = tree[hp].dat;
  87.         death[dat.second] = nd, cnt[nd]++;
  88.         pop(hp);
  89.     }
  90.     if (!hp) return hp;
  91.     if (a[nd] == 0) plus_dt(hp, b[nd]);
  92.     else mul_dt(hp, b[nd]);
  93.     return hp;
  94. }
  96. int main()
  97. {
  98.     scanf("%d%d", &n, &m);
  99.     for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
  100.     for (int i = 2; i <= n; i++) 
  101.         scanf("%d%lld%lld", &u, &a[i], &b[i]), push(u, i);
  102.     for (int i = 1; i <= m; i++){
  103.         scanf("%lld%d", &s[i], &c[i]);
  104.         v[c[i]].push_back(i);
  105.     }
  106.     depth[1] = 1;
  107.     dfs(1);
  108.     for (int i = 1; i <= n; i++) printf("%d\n", cnt[i]);
  109.     for (int i = 1; i <= m; i++) printf("%d\n", depth[c[i]]-depth[death[i]]);
  110.     return 0;
  111. }

树状数组

bzoj4415: [Shoi2013]发牌

类似约瑟夫问题，树状数组上二分小trick，貌似一年前就在千古神犇lcy的课上学习过。就是二进制一位一位确定。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 700005;
  6. inline int lowbit(int i) { return i&(-i); }
  7. int c[MAXN], n;
  8. void modify(int pos, int dt)
  9. { for (int i = pos; i <= n; i += lowbit(i)) c[i] += dt; }
  11. int sum(int k)
  12. {
  13.     int now = 0, dat = 0;
  14.     for (int i = 1<<25; i; i >>= 1) {
  15.         if (now+i <= n && dat+c[i+now] < k)
  16.             dat += c[i+now], now += i;
  17.     }
  18.     return now+1;
  19. }
  21. int query(int a)
  22. {
  23.     int ans = 0;
  24.     for (int i = a; i; i -= lowbit(i))
  25.         ans += c[i];
  26.     return ans;
  27. }
  29. int main()
  30. {
  31.     scanf("%d", &n);
  32.     for (int i = 1; i <= n; i++) modify(i, 1);
  33.     int now = 0;
  34.     for (int i = 1; i <= n; i++) {
  35.         int last = n-i+1, k;
  36.         scanf("%d", &k);
  37.         k += query(now) + 1;
  38.         int p = k%last;
  39.         if (p == 0) p = last;
  40.         now = sum(p), modify(now, -1);
  41.         printf("%d\n", now);
  42.     }
  43.     return 0;
  44. }

bzoj4418: [Shoi2013]扇形面积并

出题人大概没有学过高中数学...明明是均分之间的区间。

一开始还以为需要玄学可持久化，后来发现只需要在合适的地方打个表，然后一块一块扫过去，用树状数组kth就好。由于是寻找最大，可以通过变成最小。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 300005;
  6. int c[MAXN*10], n, m, k, r = 2000001;
  8. inline int lowbit(int i) { return i&(-i); }
  9. void modify(int nd, int dt)
  10. { for (int i = nd; i <= r; i += lowbit(i)) c[i] += dt; }
  11. int sum(int nd)
  12. { int ans = 0; for (int i = nd; i; i -= lowbit(i)) ans += c[i]; return ans; }
  13. int query(int l, int r)
  14. { return sum(r)-sum(l-1); }
  15. int kth(int nd)
  16. {
  17.     int now = 0, dat = 0;
  18.     for (int i = 1<<27; i; i >>= 1) {
  19.         if (now+i <= r && dat+c[i+now] < nd)
  20.             dat += c[i+now], now += i;
  21.     }
  22.     return now+1;
  23. }
  25. vector<int> add[MAXN*10];
  27. void solve()
  28. {
  29.     long long ans = 0;
  30.     for (int i = 1; i <= m; i++) {
  31.         for (int j = 0; j < add[i].size(); j++) {
  32.             if (add[i][j] > 0) modify(r-add[i][j]+1, 1);
  33.             else modify(r-(-add[i][j])+1, -1);
  34.         }
  35.         long long rm = r-kth(k)+1;
  36.         if (rm <= r) ans += rm*rm;
  37.     }
  38.     printf("%lld\n", ans);
  39. }
  41. int main()
  42. {
  43.     scanf("%d%d%d", &n, &m, &k);
  44.     m *= 2;
  45.     for (int i = 1; i <= n; i++) {
  46.         int r, a, b;
  47.         scanf("%d%d%d", &r, &a, &b);
  48.         if (a < 0) a += m;
  49.         if (b < 0) b += m;  
  50.         if (a < b) add[a+1].push_back(r), add[b+1].push_back(-r);
  51.         else if (a > b) 
  52.             add[1].push_back(r), add[b+1].push_back(-r), add[a+1].push_back(r);
  53.         else add[1].push_back(r);
  54.     }
  55.     solve();
  56.     return 0;
  57. }

bzoj1455: 罗马游戏

居然可以把死人和活人变成一组......昏君啊...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 1000005;
  5. struct sheap {
  6.     int lc, rc, dat;
  7.     sheap() { lc = rc = 0; }
  8. } tree[MAXN];
  10. int merge(int a, int b)
  11. {
  12.     if (a == 0 || b == 0) return a+b;
  13.     if (tree[a].dat > tree[b].dat) swap(a, b);
  14.     swap(tree[a].lc, tree[a].rc);
  15.     return tree[a].lc = merge(tree[a].lc, b), a;
  16. }
  18. set<int> st;
  20. int pop(int &a)
  21. {
  22.     int ret = tree[a].dat;
  23.     st.insert(ret);
  24.     a = merge(tree[a].lc, tree[a].rc);
  25.     return ret;
  26. }
  28. int fa[MAXN];
  29. inline int findf(int nd)
  30. { return fa[nd]?fa[nd]=findf(fa[nd]):nd; }
  31. int n, m;
  32. char str[10];
  33. int htp[MAXN], dat[MAXN];
  35. int main()
  36. {
  37.     scanf("%d", &n);
  38.     for (int i = 1; i <= n; i++) scanf("%d", &tree[i].dat), dat[i] = tree[i].dat, htp[i] = i;
  39.     scanf("%d", &m);
  40.     for (int i = 1; i <= m; i++) {
  41.         scanf("%s", str);
  42.         if (str[0] == 'M') {
  43.             int x, y;
  44.             scanf("%d%d", &x, &y);
  45.             if (st.count(dat[x]) || st.count(dat[y])) continue;
  46.             x = findf(x), y = findf(y);
  47.             if (x != y) fa[x] = y, htp[y] = merge(htp[x], htp[y]);
  48.         } else {
  49.             int x;
  50.             scanf("%d", &x);
  51.             if (st.count(dat[x])) puts("0");
  52.             else
  53.                 printf("%d\n", pop(htp[findf(x)]));
  54.         }
  55.     }
  56.     return 0;
  57. }

bzoj2006: [NOI2010]超级钢琴

堆+ST表。
堆维护表示从开始，终点在之间的区间最大值，每次取出最大值后将区间分裂。因此需要用ST表维护区间最大值和最大值位置。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 500005;
  6. long long f[MAXN][22];
  7. int pos[MAXN][22];
  8. long long a[MAXN];
  10. int n, k, l, r;
  12. inline long long max_val(int l, int r)
  13. {
  14.     int k = int(log2(r-l+1)+0.0000001);
  15.     return max(f[l][k], f[r-(1<<k)+1][k]);
  16. }
  18. inline int max_pos(int l, int r)
  19. {
  20.     int k = int(log2(r-l+1)+0.0000001);
  21.     if (f[l][k] >= f[r-(1<<k)+1][k]) return pos[l][k];
  22.     return pos[r-(1<<k)+1][k];
  23. }
  25. struct query {
  26.     int i, l, r;
  27.     inline long long val()
  28.     {
  29.         return max_val(l, r)-a[i-1];
  30.     }
  31.     inline int pos()
  32.     {
  33.         return max_pos(l, r);
  34.     }
  35.     inline friend bool operator < (query a, query b)
  36.     {
  37.         return a.val() < b.val();
  38.     }
  39. };
  41. priority_queue<query> hp;
  43. int main()
  44. {
  45.     scanf("%d%d%d%d", &n, &k, &l, &r);
  46.     for (register int i = 1; i <= n; i++)
  47.         scanf("%lld", &a[i]), a[i] += a[i-1];
  48.     for (register int i = 1; i <= n; i++) f[i][0] = a[i], pos[i][0] = i;
  49.     for (register int j = 1; j <= 21; j++)
  50.         for (register int i = 1; i <= n; i++) {
  51.             f[i][j] = f[i][j-1], pos[i][j] = pos[i][j-1];
  52.             if (i+(1<<(j-1)) <= n && f[i+(1<<(j-1))][j-1] > f[i][j]) {
  53.                 f[i][j] = f[i+(1<<(j-1))][j-1];
  54.                 pos[i][j] = pos[i+(1<<(j-1))][j-1];
  55.             }
  56.         }
  57.     for (register int i = 1; i <= n; i++)
  58.         if (i+l-1 <= n)
  59.             hp.push((query){i, i+l-1, min(n, i+r-1)});
  60.     long long ans = 0;
  61.     for (register int i = 1; i <= k; i++) {
  62.         query tp = hp.top(); hp.pop();
  63.         ans += tp.val();
  64.         int p = tp.pos();
  65.         if (p-1 >= tp.l) hp.push((query){tp.i, tp.l, p-1});
  66.         if (p+1 <= tp.r) hp.push((query){tp.i, p+1, tp.r});
  67.     }
  68.     cout << ans << endl;
  69.     return 0;
  70. }

bzoj3211: 花神游历各国

非负!=正..
如果早做了这题大概就会做出省选相逢是问候了吧...

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 100005;
  6. int fa[MAXN];
  7. inline int findf(int nd)
  8. { return fa[nd]!=nd?fa[nd] = findf(fa[nd]):nd; }
  9. inline int lowbit(int i) { return i&(-i); }
  10. long long c[MAXN], dat[MAXN];
  11. int n, m;
  12. void modify(int nd, int dt)
  13. { for (int i = nd; i <= n; i += lowbit(i)) c[i] += dt; }
  14. long long sum(int nd)
  15. { long long ans = 0; for (int i = nd; i; i -= lowbit(i)) ans += c[i]; return ans; }
  16. long long query(int l, int r)
  17. { return sum(r)-sum(l-1); }
  19. inline int read()
  20. {
  21.     int a = 0, c;
  22.     do c = getchar(); while (!isdigit(c));
  23.     while (isdigit(c)) {
  24.         a = a*10+c-'0';
  25.         c = getchar();
  26.     }
  27.     return a;
  28. }
  30. int main()
  31. {
  32.     scanf("%d", &n);
  33.     for (register int i = 1; i <= n; i++) c[i] = read(), dat[i] = c[i], fa[i] = i;
  34.     for (register int i = 1; i <= n; i++) if (i+lowbit(i)<=n) c[i+lowbit(i)] += c[i];
  35.     fa[n+1] = n+1;
  36.     scanf("%d", &m);
  37.     for (register int i = 1; i <= m; i++) {
  38.         int opt, l, r, d;
  39.         opt = read(), l = read(), r = read();
  40.         if (opt == 1) printf("%lld\n", query(l, r));
  41.         else {
  42.             while (l <= r) {
  43.                 d = dat[l]; 
  44.                 d = (int)(sqrt(d))-d;
  45.                 modify(l, d), dat[l] += d;
  46.                 if (dat[l] <= 1) fa[l] = l+1;
  47.                 l = findf(l+1);
  48.             }
  49.         }
  50.     }
  51.     return 0;
  52. }

线段树

bzoj4592: [Shoi2015]脑洞治疗仪

比较关键的是完成治疗。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 200005;
  6. int dat[MAXN*4], lc[MAXN*4], rc[MAXN*4], l[MAXN*4], r[MAXN*4];
  7. int change[MAXN*4], llen[MAXN*4], rlen[MAXN*4], len[MAXN*4], top = 0, root = 0;
  9. inline int new_node(int opl, int opr)
  10. { return ++top, l[top] = opl, r[top] = opr, top; }
  12. inline void pdw(int nd) // 1 nh / -1 hole
  13. {
  14.     if (!change[nd]) return;
  15.     change[lc[nd]] = change[rc[nd]] = change[nd]*(lc[nd]!=0);
  16.     dat[nd] = (r[nd]-l[nd]+1)*(change[nd]==1);
  17.     llen[nd] = rlen[nd] = len[nd] = (r[nd]-l[nd]+1)*(change[nd]==-1);
  18.     change[nd] = 0;
  19. }
  21. inline void update(int nd)
  22. {
  23.     pdw(nd), pdw(lc[nd]), pdw(rc[nd]);
  24.     if (l[nd] == r[nd]) {
  25.         llen[nd] = rlen[nd] = len[nd] = (dat[nd]==0);
  26.         return;
  27.     }
  28.     llen[nd] = llen[lc[nd]]+(dat[lc[nd]] == 0)*llen[rc[nd]];
  29.     rlen[nd] = rlen[rc[nd]]+(dat[rc[nd]] == 0)*rlen[lc[nd]];
  30.     len[nd] = max(max(len[lc[nd]], len[rc[nd]]), rlen[lc[nd]]+llen[rc[nd]]);
  31.     dat[nd] = dat[lc[nd]]+dat[rc[nd]];
  32. }
  34. int pat[MAXN];
  36. void build(int &nd, int l, int r)
  37. {
  38.     nd = new_node(l, r);
  39.     if (l == r) dat[nd] = pat[r];
  40.     else build(lc[nd], l, (l+r)/2), build(rc[nd], (l+r)/2+1, r);
  41.     update(nd);
  42. }
  44. void modify(int nd, int opl, int opr, int alc)
  45. {
  46.     if (opl > opr) return;
  47.     pdw(nd);
  48.     if (opl == l[nd] && opr == r[nd]) change[nd] = alc, pdw(nd);
  49.     else {
  50.         int mid = (l[nd]+r[nd])/2;
  51.         if (opr <= mid) modify(lc[nd], opl, opr, alc);
  52.         else if (opl > mid) modify(rc[nd], opl, opr, alc);
  53.         else modify(lc[nd], opl, mid, alc), modify(rc[nd], mid+1, opr, alc);
  54.         pdw(lc[nd]), pdw(rc[nd]), update(nd);
  55.     }
  56. }
  58. int query(int nd, int opl, int opr)
  59. {
  60.     pdw(nd);
  61.     if (opl == l[nd] && opr == r[nd]) return len[nd];
  62.     else {
  63.         int mid = (l[nd]+r[nd])/2;
  64.         pdw(lc[nd]), pdw(rc[nd]);
  65.         if (opr <= mid) return query(lc[nd], opl, opr);
  66.         else if (opl > mid) return query(rc[nd], opl, opr);
  67.         else return max(max(query(lc[nd], opl, mid), query(rc[nd], mid+1, opr)), 
  68.                 min(rlen[lc[nd]], mid-opl+1)+min(llen[rc[nd]], opr-mid));
  69.     }
  70. }
  72. void dfs(int nd, int tab = 0)
  73. {
  74.     if (!nd) return;
  75.     for (int i = 1; i <= tab; i++) putchar(' ');
  76.     printf("[%d, %d], dat = %d, llen = %d, rlen = %d, len = %d, change = %d\n", l[nd], r[nd], dat[nd], llen[nd], rlen[nd], len[nd], change[nd]);
  77.     dfs(lc[nd], tab+2), dfs(rc[nd], tab+2);
  78. }
  80. int query_sum(int nd, int opl, int opr)
  81. {
  82.     if (opl > opr) return 0;
  83.     pdw(nd);
  84.     int mid = (l[nd]+r[nd])/2;
  85.     if (opl == l[nd] && opr == r[nd]) return dat[nd];
  86.     else return query_sum(lc[nd], opl, min(opr, mid))+query_sum(rc[nd], max(opl, mid+1), opr);
  87. }
  89. int last_pos(int nd, int k) // in node nd, the first place to have k holes
  90. {
  91.     if (l[nd] == r[nd]) return l[nd];
  92.     pdw(nd), pdw(lc[nd]), pdw(rc[nd]);
  93.     int lp = r[lc[nd]]-l[lc[nd]]+1-dat[lc[nd]];
  94.     if (lp >= k) return last_pos(lc[nd], k);
  95.     else return last_pos(rc[nd], k-lp);
  96. }
  98. void fix(int ll, int lr, int nl, int nr)
  99. {
  100.     int dt = query_sum(root, ll, lr);
  101.     modify(root, ll, lr, -1);
  102.     if (dt == 0) return;
  103.     int k = last_pos(root, nl-1-query_sum(root, 1, nl-1)+dt);
  104.     modify(root, nl, min(nr, k), 1);
  105. }
  107. inline int read()
  108. {
  109.     int a = 0, c;
  110.     do c = getchar(); while (!isdigit(c));
  111.     while (isdigit(c))
  112.         a = a*10+c-'0', c = getchar();
  113.     return a;
  114. }
  116. int n, m;
  118. int main()
  119. {
  120.     n = read(), m = read();
  121.     for (int i = 1; i <= n; i++) pat[i] = 1;
  122.     build(root, 1, n);
  123.     for (int i = 1; i <= m; i++) {
  124.         int tp, l, r, u, v;
  125.         tp = read();
  126.         if (tp == 0) l = read(), r = read(), modify(root, l, r, -1);
  127.         else if (tp == 1) l = read(), r = read(), u = read(), v = read(), fix(l, r, u, v);
  128.         else l = read(), r = read(), printf("%d\n", query(root, l, r));
  129.     }
  130.     return 0;
  131. }

bzoj2212: [Poi2011]Tree Rotations

线段树合并小技巧。
貌似空间是的？

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int MAXN = 400005;
  6. struct node {
  7.     int l, r, lc, rc, dat;
  8. } tree[MAXN*4];
  9. int top = 0, root = 0;
  10. long long c1, c2;
  12. int build(int l, int r, int pos)
  13. {
  14.     if (l == r) return tree[++top] = (node){l, r, 0, 0, 1}, top;
  15.     int mid = (l+r)>>1, nd = ++top;
  16.     tree[nd] = (node){l, r, 0, 0, 1};
  17.     if (pos <= mid) return tree[nd].lc = build(l, mid, pos), nd;
  18.     else return tree[nd].rc = build(mid+1, r, pos), nd;
  19. }
  21. int merge(int a, int b)
  22. {
  23.     if (a == 0 || b == 0) return a+b;
  24.     // cerr << "Merging " << a << " " << b << endl;
  25.     // display(a, 0), display(b, 0);
  26.     c1 += (long long)tree[tree[a].lc].dat*tree[tree[b].rc].dat;
  27.     c2 += (long long)tree[tree[b].lc].dat*tree[tree[a].rc].dat;
  28.     tree[a].dat += tree[b].dat;
  29.     tree[a].lc = merge(tree[a].lc, tree[b].lc);
  30.     tree[a].rc = merge(tree[a].rc, tree[b].rc);
  31.     return a;
  32. }
  34. int n;
  35. long long cnt = 0, cp = 0;
  37. int dfs()
  38. {
  39.     int nd; scanf("%d", &nd);
  40.     if (nd != 0) return build(1, n, nd);
  41.     ++cp;
  42.     int t = cp;
  43.     int x = dfs(), y = dfs();
  44.     c1 = c2 = 0;
  45.     int ret = merge(x, y);
  46.     cnt += min(c1, c2);
  47.     return ret;
  48. }
  50. int main()
  51. {
  52.     scanf("%d", &n);
  53.     dfs();
  54.     printf("%lld\n", cnt);
  55.     return 0;
  56. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注