【P4211 LNOI2014】LCA——树链剖分 +询问离线

谁借莪１个温暖的怀抱￠ 2021-11-05 05:36 212阅读 0赞

（7.16晚）更完先在B站颓一会儿……

\---------------------------------------------------------------

（以下为luogu题面）

## 题目描述 ##

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。 设dep\[i\]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。 有q次询问，每次询问给出l r z，求∑（l≤i≤r dep\[LCA(i,z)\]）

## 输入输出格式 ##

**输入格式：**

第一行2个整数n q。 接下来n-1行，分别表示点1到点n-1的父节点编号。 接下来q行，每行3个整数l r z。

**输出格式：**

输出q行，每行表示一个询问的答案。每个答案对201314取模输出

## 说明 ##

共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。

需要说明的是，这道题的思路跟LCA的三种求法无关（树剖太暴力了，而且确实会用到树剖），也就是说没有丝毫的暴力分可拿。（掀桌）

从这道题中对于深度的定义可以发现，两个点LCA的深度等价于它们的公共祖先的数目。那么问题的本质是，每次给定一个点集，求集合中每个点与一个定点的祖先数目的累计。考虑这样的暴力处理：对于任取一个点u与所给定点z，我们可以先给u的每个祖先都打一层标记，然后询问从z到根有标记的点的数目。这个过程显然可以用树剖处理，我们在树剖序上架一个线段树支持区间修改、区间查询，每个这样的询问可以做到log^2n

的复杂度。

如果我们对每次询问，都把点集中的每个点这样打一遍祖先的标记再查询z，总复杂度会多出一个q来，显然需要进一步优化。题中给出的点集有一个非常好的性质：点集中的点处于一段连续区间中。那么，我们可以把每个询问\[l, r\]差分为\[1, l - 1\]和\[1, r\]两个询问，那么需要维护的就只有形如\[1, R\]与每个z的关系了。

因此我们把询问离线差分后按右端点排序，从左向右扫描点集\[1, n\]并打标记，每遇到一个询问则查询给定z与根之间的标记数目，统计进询问数组即可。

代码：

1.  \#include <cstdio>  
2.  \#include <iostream>  
3.  \#include <cstring>  
4.  \#include <algorithm>  
5.  \#define lowbit(i) (i & -i)  
6.  \#define maxn 50010  
7.  \#define mod 201314  
8.  template <typename T>  
9.  void read(T &x) \{  
10.     x = 0;  
11.     int f = 1;  
12.     char ch = getchar();  
13.     while (!isdigit(ch)) \{  
14.         if (ch == '-')  
15.             f = -1;  
16.         ch = getchar();  
17.     \}  
18.     while (isdigit(ch)) \{  
19.         x = x \* 10 + (ch ^ 48);  
20.         ch = getchar();  
21.     \}  
22.     x \*= f;  
23.     return;  
24. \}  
25. using namespace std;  
26. int head\[maxn\], top;  
27. struct E \{  
28.     int to, nxt;  
29. \} edge\[maxn\];  
30. inline void insert(int u, int v) \{  
31.     edge\[++top\] = (E) \{v, head\[u\]\};  
32.     head\[u\] = top;  
33. \}  
34. int n, q, ans\[maxn\], qtp;  
35. struct Q \{  
36.     int r, z, id;  
37.     bool op;  
38.     friend bool operator < (Q a, Q b) \{  
39.         return a.r < b.r;  
40.     \}  
41. \} ask\[maxn << 1\];  
42. /\*namespace BIT \{ 
43.     int bit\[maxn\]; 
44.     void modify(int x, int val) \{ 
45.         for (int i = x; i <= n; i += lowbit(i))   
46.             bit\[i\] += val; 
47.     \} 
48.     int presum(int x) \{ 
49.         int sum = 0; 
50.         for (int i = x; i; i -= lowbit(i)) 
51.             sum = (sum + bit\[i\]) % mod; 
52.         return sum; 
53.     \} 
54. \}\*/  
55. namespace Segment\_tree \{  
56.     \#define lc (nd<<1)  
57.     \#define rc ((nd<<1)|1)  
58.     \#define mid ((l+r)>>1)  
59.     struct node \{  
60.         int val, len;  
61.         friend node operator + (node a, node b) \{  
62.             return (node) \{(a.val + b.val) % mod, a.len + b.len\};  
63.         \}  
64.     \} seg\[maxn << 2\];  
65.     int tag\[maxn << 2\];  
66.     inline void update(int nd) \{  
67.         seg\[nd\] = seg\[lc\] + seg\[rc\];  
68.     \}  
69.     inline void put\_tag(int nd, int op) \{  
70.         seg\[nd\].val += op \* seg\[nd\].len;  
71.         tag\[nd\] += op;  
72.     \}  
73.     inline void push\_down(int nd) \{  
74.         put\_tag(lc, tag\[nd\]);  
75.         put\_tag(rc, tag\[nd\]);  
76.         tag\[nd\] = 0;  
77.     \}  
78.     void build(int nd, int l, int r) \{  
79.         if (l == r) \{  
80.             seg\[nd\] = (node) \{0, 1\};  
81.             return;  
82.         \}  
83.         build(lc, l, mid);  
84.         build(rc, mid + 1, r);  
85.         update(nd);  
86.     \}  
87.     void modify(int nd, int l, int r, int ql, int qr, int val) \{  
88.         if (l >= ql && r <= qr) \{  
89.             put\_tag(nd, val);  
90.             return;  
91.         \} else if (l > qr || r < ql)  
92.             return;  
93.         push\_down(nd);  
94.         modify(lc, l, mid, ql, qr, val);  
95.         modify(rc, mid + 1, r, ql, qr, val);  
96.         update(nd);  
97.         return;  
98.     \}  
99.     int query(int nd, int l, int r, int ql, int qr) \{  
100.         if (l >= ql && r <= qr)     
101.             return seg\[nd\].val;  
102.         if (l > qr || r < ql)  
103.             return 0;  
104.         push\_down(nd);  
105.         return (query(lc, l, mid, ql, qr) + query(rc, mid + 1, r, ql, qr)) % mod;  
106.     \}  
107. \}  
108. namespace Div\_tree \{  //树剖
109. //  using namespace BIT;  //试图用树状数组维护区间修改的惨痛失败  
    
110.     using namespace Segment\_tree;  
111.     int dfn\[maxn\], size\[maxn\], ftop\[maxn\], d\[maxn\], son\[maxn\], f\[maxn\];  
112.     int tmr;  
113.     void dfs1(int u, int pre) \{  
114.         f\[u\] = pre;  
115.         d\[u\] = d\[pre\] + 1;  
116.         size\[u\] = 1;  
117.         for (int i = head\[u\]; i; i = edge\[i\].nxt) \{  
118.             int v = edge\[i\].to;  
119.             dfs1(v, u);  
120.             size\[u\] += size\[v\];  
121.             if (size\[v\] > size\[son\[u\]\])  
122.                 son\[u\] = v;  
123.             \}  
124.     \}  
125.     void dfs2(int u, int tp) \{  
126.         dfn\[u\] = ++tmr;  
127.         ftop\[u\] = tp;  
128.         if (!son\[u\])      
129.             return;  
130.         dfs2(son\[u\], tp);  
131.         for (int i = head\[u\]; i; i = edge\[i\].nxt) \{  
132.             int v = edge\[i\].to;  
133.             if (v != son\[u\])  
134.                 dfs2(v, v);  
135.         \}  
136.     \}  
137.     void Mrange(int u, int v, int val) \{  
138.         while (ftop\[u\] != ftop\[v\]) \{  
139.             if (d\[ftop\[u\]\] < d\[ftop\[v\]\])  
140.                 swap(u, v);  
141.             modify(1, 1, n, dfn\[ftop\[u\]\], dfn\[u\], val);  
142.             u = f\[ftop\[u\]\];  
143.         \}  
144.         if (d\[u\] < d\[v\]) swap(u, v);  
145.         modify(1, 1, n, dfn\[v\], dfn\[u\], val);  
146.         return;  
147.     \}  
148.     int Qrange(int u, int v) \{  
149.         int sum = 0;  
150.         while (ftop\[u\] != ftop\[v\]) \{  
151.             if (d\[ftop\[u\]\] < d\[ftop\[v\]\])  
152.                 swap(u, v);  
153.             sum = (sum + query(1, 1, n, dfn\[ftop\[u\]\], dfn\[u\])) % mod;   
154.             u = f\[ftop\[u\]\];  
155.         \}  
156.         if (d\[u\] < d\[v\]) swap(u, v);  
157.         sum += query(1, 1, n, dfn\[v\], dfn\[u\]);  
158.         return sum % mod;  
159.     \}  
160. \} using namespace Div\_tree;  
161. void init() \{  
162.     build(1, 1, n);  
163.     dfs1(1, 0);  
164.     dfs2(1, 1);  
165. \}  
166. int main() \{  
167.     read(n), read(q);  
168.     int u, v, z;  
169.     for (int i = 2; i <= n; ++i)//编号+1   
170.         read(u), ++u, insert(u, i);  
171.     for (int i = 1; i <= q; ++i) \{  
172.         read(u), read(v), read(z);  
173.         ask\[++qtp\] = (Q) \{u, z+1, i, 0\};  //拆询问
174.         ask\[++qtp\] = (Q) \{v+1, z+1, i, 1\};  
175.     \}  
176.     sort(ask + 1, ask + qtp + 1);  
177.     init();  
178.     int i = 0, j = 1;  
179.     while (j <= qtp) \{  
180.         while (i < ask\[j\].r)  
181.             Mrange(1, ++i, 1);  
182.         if (ask\[j\].op)  
183.         ans\[ask\[j\].id\] += Qrange(1, ask\[j\].z);  //按标记统计进答案
184.         else ans\[ask\[j\].id\] -= Qrange(1, ask\[j\].z);  
185.         ++j;  
186.     \}  
187.     for (int i = 1; i <= q; ++i)  
188.         printf("%d\\n", (ans\[i\]+mod)%mod);  
189.     return 0;  
190. \}

转载于:https://www.cnblogs.com/TY02/p/11196670.html