【BZOJ3626】【LNOI2014】LCA （树剖+离线）

Description

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。
（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）答案对201314取模。

这个题是大饺子安利给我的，然后顺带学了一发树剖（好弱啊）。

这个题解讲的很好啦w：http://www.cnblogs.com/JoeFan/p/4229141.html

maya代码慢的不忍直视 qwq4332 ms

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <iostream>
  4 #include <algorithm>
  5 #define p 201314
  6 #define MaxN 50010
  7 #define MaxM 100010
  8 #define LL long long
  9 
 10 using namespace std;
 11 int n, q, tot = 0;
 12 int ans[MaxN], HEAD[MaxN];
 13 struct rec{
 14     int nxt, z, ord, ty;
 15 }da[MaxM];
 16 
 17 void read(int &x){
 18     x = 0; char c = getchar();
 19     while (c < '0' || c > '9') c = getchar();
 20     while (c >= '0' && c <= '9') x = x*10 + c-'0', c = getchar();
 21 }
 22 
 23 namespace Segtree{
 24     int S = 0, root = 1;
 25     int ch[MaxM][2];
 26     LL mark[MaxM], tree[MaxM], len[MaxM];
 27     
 28     #define l ch[x][0]
 29     #define r ch[x][1]
 30     
 31     void updata(int x, LL c){
 32         if (!x) return;
 33         tree[x] = tree[x] + len[x] * c;
 34         mark[x] += c;
 35     }
 36     
 37     void Merge(int x){
 38         len[x] = len[l]+len[r];
 39         tree[x] = tree[l] + tree[r];
 40     }
 41     
 42     void down(int x){
 43         updata(l, mark[x]);
 44         updata(r, mark[x]);    
 45         mark[x] = 0ll;
 46     }    
 47     
 48     void Build(int &x, int a, int b){
 49         x = ++S;
 50         //cout<<x<<" "<<a<<" "<<b<<endl;
 51         if (a == b) {
 52             len[x] = 1ll; return;
 53         }
 54         int mid = (a+b) >> 1;
 55         Build(ch[x][0], a, mid);
 56         Build(ch[x][1], mid+1, b);
 57         Merge(x);
 58     }
 59     
 60     void change(int x, int a, int b, int L, int R, LL c){
 61         down(x);
 62         //printf("x:%d l:%d r:%d L:%d R:%d
", x, a, b, L, R);
 63         if (L <= a && R >= b){
 64             updata(x, c);
 65             return;
 66         }
 67         int mid = (a+b) >> 1;
 68         if (L <= mid) change(l, a, mid, L, R, c);
 69         if (R > mid) change(r, mid+1, b, L, R, c);
 70         Merge(x);
 71     }
 72     
 73     LL query(int x, int a, int b, int L, int R){
 74         down(x);
 75         if (L <= a && R >= b) return tree[x];
 76         LL ret = 0ll;
 77         int mid = (a+b) >> 1;
 78         if (L <= mid) ret += query(l, a, mid, L, R);
 79         if (R > mid) ret += query(r, mid+1, b, L, R);
 80         Merge(x);
 81         return ret;        
 82     }
 83     
 84 };
 85 
 86 
 87 #undef l
 88 #undef r
 89 
 90 namespace HL_Decomp{
 91     int S = 0, cnt = 0;
 92     int head[MaxN], dfn[MaxN], depth[MaxN], son[MaxN], fa[MaxN], sz[MaxN], top[MaxN];
 93     struct road{
 94         int v, nxt;
 95     }E[MaxM];
 96     
 97     void adde(int u, int v){
 98         E[++S] = (road) {v, head[u]};
 99         head[u] = S;
100     }
101     
102     void dfs1(int u){
103         sz[u] = 1;
104         int MaxSon = 0;
105         for (int i = head[u], v; i; i = E[i].nxt){
106             v = E[i].v;
107             if (v == fa[u]) continue;
108             fa[v] = u; depth[v] = depth[u]+1;
109             dfs1(v); sz[u] += sz[v];
110             if (sz[v] > MaxSon) MaxSon = sz[v], son[u] = v;
111         }
112     }
113     
114     void dfs2(int u, int Top){
115         if (!u) return;
116         top[u] = Top; dfn[u] = ++cnt;
117         dfs2(son[u], Top);
118         for (int i = head[u]; i; i = E[i].nxt) {
119             if (E[i].v != son[u] && E[i].v != fa[u]) dfs2(E[i].v, E[i].v);
120         }
121     }
122     
123     void change(int u, int v, LL c){
124         while (top[u] != top[v]){
125             if (depth[top[u]] > depth[top[v]]) std::swap(u, v);
126             Segtree::change(1, 1, n, dfn[top[v]], dfn[v], c);
127             v = fa[top[v]];
128         }
129         if (depth[u] > depth[v]) std::swap(u, v);
130         Segtree::change(1, 1, n, dfn[u], dfn[v], c);
131     }
132     
133     LL query(int u, int v){
134         LL ret = 0ll;
135         while (top[u] != top[v]){
136             if (depth[top[u]] > depth[top[v]]) std::swap(u, v);
137             ret += Segtree::query(1, 1, n, dfn[top[v]], dfn[v]);
138             v = fa[top[v]];
139         }
140         if (depth[u] > depth[v]) std::swap(u, v);
141         ret += Segtree::query(1, 1, n, dfn[u], dfn[v]);
142         return ret % p;
143     }
144     
145 }
146 
147 void Read_Data(){
148     read(n); read(q);
149     for (int i = 2, u; i <= n; i++) {
150         read(u);
151         HL_Decomp::adde(u+1, i);
152     }
153 }
154 
155 void ADD(int a, int b, int c, int d){
156     da[++tot] = (rec) {HEAD[a], b, c, d};
157     HEAD[a] = tot;
158 }
159 
160 void Solve(){
161     int Root;
162     HL_Decomp::dfs1(1);
163     HL_Decomp::dfs2(1, 1);
164     Segtree::Build(Root, 1, n);
165     for (int i = 1, l, r, z; i <= q; i++) {
166         read(l); read(r); read(z); l++, r++, z++;
167         ADD(l-1, z, i, -1); ADD(r, z, i, 1);
168     }
169     for (int i = 1; i <= n; i++){
170         HL_Decomp::change(1, i, 1ll);
171         for (int j = HEAD[i]; j; j = da[j].nxt){
172             ans[da[j].ord] += (int)HL_Decomp::query(1, da[j].z) * da[j].ty;
173         }
174     }
175     for (int i = 1; i <= q; i++) printf("%d
", (ans[i] + p) % p);
176 }
177 
178 int main()
179 {
180     Read_Data();
181     Solve();
182     return 0;
183 }