CPP   8

segtree

Guest on 12th October 2021 10:46:25 AM

  1. #include <bits/stdc++.h>
  2. #define segmid ((l + r) >> 1)
  3. using namespace std;
  4. const int maxn = 400005;
  5. int fa[maxn], dep[maxn], top[maxn], size[maxn], son[maxn], id[maxn], rnk[maxn],
  6.     cnt;
  7. int ins[maxn];
  8. vector<int> e[maxn];
  9.  
  10. int n, q;
  11. namespace segtree {
  12.     int segins[maxn];
  13.     void build(int l, int r, int rt) {
  14.         if (l == r) {
  15.             segins[rt] = 0;
  16.             return;
  17.         }
  18.         build(l, segmid, rt * 2);
  19.         build(segmid + 1, r, rt * 2 + 1);
  20.         segins[rt] = 0;
  21.     }
  22.     void change(int l, int r, int x, bool val, int rt) {
  23.         if (l == r) {
  24.             segins[rt] = val;
  25.             return;
  26.         }
  27.         if (x <= segmid) {
  28.             change(l, segmid, x, val, rt * 2);
  29.  
  30.         } else {
  31.             change(segmid + 1, r, x, val, rt * 2 + 1);
  32.         }
  33.         segins[rt] = segins[rt * 2] + segins[rt * 2 + 1];
  34.     }
  35.  
  36.     int getSum(int l, int r, int u, int v, int rt) {
  37.         if (u > v) swap(u, v);
  38.         if (l == r) {
  39.             return segins[rt];
  40.         }
  41.         if (u > segmid) {
  42.             // ???
  43.             return getSum(segmid + 1, r, u, v, rt * 2 + 1);
  44.         } else if (v <= segmid) {
  45.             // ???
  46.             return getSum(l, segmid, u, v, rt * 2);
  47.         } else {
  48.             return getSum(l, segmid, u, segmid, rt * 2) +
  49.                    getSum(segmid + 1, r, segmid + 1, v, rt * 2 + 1);
  50.         }
  51.     }
  52. }  // namespace segtree
  53.  
  54. void dfs1(int x, int fat) {
  55.     fa[x] = fat;
  56.     dep[x] = dep[fat] + 1;
  57.     size[x] = 1;
  58.     for (int i = 0; i < e[x].size(); i++) {
  59.         int z = e[x][i];
  60.         if (z == fat) continue;
  61.         dfs1(z, x);
  62.         size[x] += size[z];
  63.         if (size[z] > size[son[x]]) son[x] = z;
  64.     }
  65. }
  66.  
  67. void dfs2(int x, int topz) {
  68.     top[x] = topz;
  69.     id[x] = ++cnt;
  70.     rnk[cnt] = x;
  71.     if (son[x] == 0) return;
  72.     dfs2(son[x], topz);
  73.     for (int i = 0; i < e[x].size(); i++) {
  74.         int z = e[x][i];
  75.         if (z == fa[x]) continue;
  76.         if (son[x] != z) {
  77.             dfs2(z, z);
  78.         }
  79.     }
  80. }
  81. void treeUpdate(int u, int t) { segtree::change(1, n, id[u], t, 1); }
  82. int treeQnodeCnt;
  83. int treeNodeCnt(int x, int y) {
  84.     if (id[x] > id[y])
  85.         return id[x] - id[y] + 1;
  86.     else
  87.         return id[y] - id[x] + 1;
  88. }
  89. int treeQsum(int u, int v) {
  90.     treeQnodeCnt = 0;
  91.     int ans = 0;
  92.     while (top[u] != top[v]) {
  93.         // Chain Jump
  94.         if (dep[top[u]] < dep[top[v]]) swap(u, v);
  95.         ans += segtree::getSum(1, n, id[top[u]], id[u], 1);
  96.         treeQnodeCnt += treeNodeCnt(top[u], u);
  97.         u = fa[top[u]];
  98.     }
  99.     treeQnodeCnt += treeNodeCnt(u, v);
  100.  
  101.     return ans + segtree::getSum(1, n, id[u], id[v], 1);
  102. }
  103.  
  104. void treeInstall(int u, int v) {
  105.     int temp1, temp2;
  106.     while (top[u] != top[v]) {
  107.         // Chain Jump
  108.         if (dep[top[u]] < dep[top[v]]) swap(u, v);
  109.         temp1 = id[u];
  110.         temp2 = id[top[u]];
  111.         if (temp1 > temp2) swap(temp1, temp2);
  112.         for (int i = temp1; i <= temp2; i++) {
  113.             segtree::change(1, n, i, 1, 1);
  114.         }
  115.  
  116.         u = fa[top[u]];
  117.     }
  118.     temp1 = id[u];
  119.     temp2 = id[v];
  120.     if (temp1 > temp2) swap(temp1, temp2);
  121.     for (int i = temp1; i <= temp2; i++) {
  122.         segtree::change(1, n, i, 1, 1);
  123.     }
  124. }
  125.  
  126. int treeUninstall(int x) {
  127.     int summ = 0;
  128.     segtree::change(1, n, id[x], 0, 1);
  129.     summ++;
  130.     // cout << "LOG uninstalled (" << x - 1 << ")" << endl;
  131.     for (int i = 0; i < e[x].size(); i++) {
  132.         int z = e[x][i];
  133.         if (z == fa[x] || !segtree::getSum(1, n, id[z], id[z], 1)) continue;
  134.         summ += treeUninstall(z);
  135.     }
  136.     return summ;
  137. }
  138.  
  139. int main() {
  140.     ios::sync_with_stdio(false);
  141.     cin.tie(0);
  142.     {  // ??????
  143.         cin >> n;
  144.         for (int i = 2; i <= n; i++) {
  145.             int a;
  146.             cin >> a;
  147.             e[i].push_back(a + 1);
  148.             e[a + 1].push_back(i);
  149.         }
  150.         memset(segtree::segins, 0, maxn);
  151.  
  152.     }  // ??????
  153.     n++;
  154.  
  155.     {  // ????
  156.         dfs1(1, 0);
  157.         // cout << "[debug] dfs1 done" << endl;
  158.         dfs2(1, 1);
  159.         // cout << "[debug] dfs2 done" << endl;
  160.         segtree::build(1, n, 1);
  161.         //        for (int i = 1; i <= n; i++) {
  162.         //            cout << "SEGTREE info: " << segtree::getMax(1, n, i, i, 1)
  163.         //            << endl;
  164.         //        }
  165.     }  // ????
  166.  
  167.     {  // ??
  168.         cin >> q;
  169.         while (q--) {
  170.             string op;
  171.             int u;
  172.             cin >> op >> u;
  173.             if (op == "install") {
  174.                 if (segtree::getSum(1, n, id[u + 1], id[u + 1], 1)) {
  175.                     cout << 0 << '\n';
  176.                     continue;
  177.                 }
  178.                 int sum = treeQsum(1, u + 1);
  179.                 cout << treeQnodeCnt - sum << '\n';
  180.                 // treeUpdate(u + 1, 1);
  181.                 treeInstall(1, u + 1);
  182.             } else {
  183.                 if (!segtree::getSum(1, n, id[u + 1], id[u + 1], 1)) {
  184.                     cout << 0 << '\n';
  185.                     continue;
  186.                 }
  187.                 // op == "uninstall"
  188.                 cout << treeUninstall(u + 1) << '\n';
  189.             }
  190.         }
  191.     }  // ??
  192.     return 0;
  193. }

Raw Paste


Login or Register to edit or fork this paste. It's free.