[luoguP2146] 软件包管理器（树链剖分）

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 #define root 1, 1, n
  6 #define ls now << 1, l, mid
  7 #define rs now << 1 | 1, mid + 1, r
  8 
  9 const int MAXN = 1000001;
 10 int n, m, cnt, tim, ans;
 11 int head[MAXN], to[MAXN], next[MAXN];
 12 int f[MAXN], son[MAXN], size[MAXN], deep[MAXN], tid[MAXN], top[MAXN], sum[MAXN << 2], turn[MAXN << 2];
 13 
 14 inline int read()
 15 {
 16     int f = 1, x = 0;
 17     char ch = getchar();
 18     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
 19     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
 20     return x * f;
 21 }
 22 
 23 inline void add(int x, int y)
 24 {
 25     to[cnt] = y;
 26     next[cnt] = head[x];
 27     head[x] = cnt++;
 28 }
 29 
 30 inline void dfs1(int u)
 31 {
 32     int i, v;
 33     size[u] = 1;
 34     deep[u] = deep[f[u]] + 1;
 35     for(i = head[u]; i != -1; i = next[i])
 36     {
 37         v = to[i];
 38         dfs1(v);
 39         size[u] += size[v];
 40         if(son[u] == -1 || size[son[u]] < size[v]) son[u] = v;
 41     }
 42 }
 43 
 44 inline void dfs2(int u, int tp)
 45 {
 46     int i, v;
 47     top[u] = tp;
 48     tid[u] = ++tim;
 49     if(son[u] != -1) dfs2(son[u], tp);
 50     for(i = head[u]; i != -1; i = next[i])
 51     {
 52         v = to[i];
 53         if(v != son[u]) dfs2(v, v);
 54     }
 55 }
 56 
 57 inline void swap(int &x, int &y)
 58 {
 59     x ^= y ^= x ^= y;
 60 }
 61 
 62 inline void pushup(int now)
 63 {
 64     sum[now] = sum[now << 1] + sum[now << 1 | 1];
 65 }
 66 
 67 inline void pushdown(int now, int len)
 68 {
 69     if(turn[now] == -1) return;
 70     sum[now << 1] = turn[now] * (len - (len >> 1));
 71     sum[now << 1 | 1] = turn[now] * (len >> 1);
 72     turn[now << 1] = turn[now];
 73     turn[now << 1 | 1] = turn[now];
 74     turn[now] = -1;
 75 }
 76 
 77 inline void update(int x, int ql, int qr, int now, int l, int r)
 78 {
 79     if(ql <= l && r <= qr)
 80     {
 81         ans += std::abs(x * (r - l + 1) - sum[now]);
 82         sum[now] = (r - l + 1) * x;
 83         turn[now] = x;
 84         return;
 85     }
 86     if(r < ql || l > qr) return;
 87     pushdown(now, r - l + 1);
 88     int mid = (l + r) >> 1;
 89     update(x, ql, qr, ls);
 90     update(x, ql, qr, rs);
 91     pushup(now);
 92 }
 93 
 94 inline void qupdate(int x, int u, int v)
 95 {
 96     while(top[u] != top[v])
 97     {
 98         if(deep[top[u]] < deep[top[v]]) swap(u, v);
 99         update(x, tid[top[u]], tid[u], root);
100         u = f[top[u]];
101     }
102     if(deep[u] > deep[v]) swap(u, v);
103     update(x, tid[u], tid[v], root);
104 }
105 
106 int main()
107 {
108     int i, x;
109     char s[10];
110     n = read();
111     memset(son, -1, sizeof(son));
112     memset(head, -1, sizeof(head));
113     memset(turn, -1, sizeof(turn));
114     for(i = 1; i < n; i++)
115     {
116         x = read();
117         f[i] = x;
118         add(x, i);
119     }
120     dfs1(0);
121     dfs2(0, 0);
122     m = read();
123     for(i = 1; i <= m; i++)
124     {
125         scanf("%s", s);
126         x = read();
127         ans = 0;
128         if(s[0] == 'i') qupdate(1, 0, x);
129         else update(0, tid[x], tid[x] + size[x] - 1, root);
130         printf("%d\n", ans);
131     }
132     return 0;
133 }