BZOJ3626【LNOI2014】LCA <离线+树链剖分>

Posted on Symbols count in article: 1.1k Reading time ≈ 4 mins.

Problem

【LNOI2014】LCA

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

给出一个nn个节点的有根树（编号为00到n−1n-1，根节点为00）。一个点的深度定义为这个节点到根的距离+1这个节点到根的距离+1。设depidep_i表示点ii的深度，lcai,jlca_{i,j}表示ii与jj的最近公共祖先。
有qq次询问，每次询问给出l,r,zl,r,z，求∑l<=i<=rdeplcai,z\sum_{l<=i<=r}dep_{lca_{i,z}}。

Input

第一行22个整数n,qn,q。
接下来n−1n-1行，分别表示点11到点n−1n-1的父节点编号。
接下来qq行，每行33个整数l,r,zl,r,z。

Output

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

Sample Input

1
2
3
4
5
6
7
5 2
0
0
1
1
1 4 3
1 4 2

Sample Output

1
2
8
5

HINT

共55组数据，nn与qq的规模分别为1000010000,2000020000,3000030000,4000040000,5000050000。

Source

数据已加强  By  \;\mathrm{By\;}saffah

标签：树链剖分

Solution

傻逼树链剖分，练手居然还WA\mathrm{WA}了一发…

首先有一个这样的暴力：对于每个询问，将zz到根的路径打标记，枚举l∼rl\sim r，每次累加当前节点最近的标记节点的深度。
然后发现可以反转一下：对于每个询问，枚举l∼rl\sim r，每次将当前结点到根路径上的所有结点权值+1+1，统计zz到根路径上的总权值即可。（权值+1+1相当于深度累加）。
这道题没有强制在线，于是可以把所有的询问都离线下来，拆成两个前缀询问[1,l−1][1,l-1]和[1,r][1,r]分别计算。如果将所有前缀询问按右端点位置排序，不难发现可以依次操作，每次将一个新的结点到根路径上的所有结点权值+1+1，操作完统计右端点在此结点上的所有前缀询问的答案。
注意模完两个前缀答案相减后可能出现负数，需要先加上MOD\mathrm{MOD}。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define MOD 201314
#define MAX_N 50000
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
vector <int> G[MAX_N+5];
struct node {int t, p, id; bool f;} opt[(MAX_N<<1)+5];
int n, m, ind, ans[MAX_N+5], tr[MAX_N<<2], tag[MAX_N<<2];
int dep[MAX_N+5], fa[MAX_N+5], sz[MAX_N+5], son[MAX_N+5], top[MAX_N+5], dfn[MAX_N+5];
bool cmp(const node &x, const node &y) {return x.t <= y.t;}
void DFS(int u) {
    sz[u] = 1;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i]; if (v == fa[u]) continue;
        dep[v] = dep[u]+1, fa[v] = u, DFS(v), sz[u] += sz[v];
        if (!son[u] || sz[son[u]] < sz[v]) son[u] = v;
    }
}
void DFS(int u, int tp) {
    top[u] = tp, dfn[u] = ++ind; if (son[u]) DFS(son[u], tp);
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if (((v = G[u][i])^fa[u]) && (v^son[u])) DFS(v, v);
}
void update(int v) {tr[v] = tr[v<<1]+tr[v<<1|1];}
void downtag(int v, int s, int t) {
    if (!tag[v]) return;
    int x = tag[v]; tag[v] = 0;
    (tr[v<<1] += x*(mid-s+1)%MOD) %= MOD;
    (tr[v<<1|1] += x*(t-mid)%MOD) %= MOD;
    (tag[v<<1] += x) %= MOD, (tag[v<<1|1] += x) %= MOD;
}
void modify(int v, int s, int t, int l, int r, int x) {
    if (s >= l && t <= r) {
        (tr[v] += x*(t-s+1)%MOD) %= MOD;
        (tag[v] += x) %= MOD; return;
    }
    downtag(v, s, t);
    if (l <= mid) modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, x);
    update(v);
}
int query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return (tr[v]+MOD)%MOD;
    int ret = 0; downtag(v, s, t);
    if (l <= mid) (ret += query(v<<1, s, mid, l, r)) %= MOD;
    if (r >= mid+1) (ret += query(v<<1|1, mid+1, t, l, r)) %= MOD;
    return (ret%MOD+MOD)%MOD;
}
void change(int u) {
    for (; u; u = fa[top[u]])
        modify(1, 1, n, dfn[top[u]], dfn[u], 1);
}
int getsum(int u) {
    int ret = 0;
    for (; u; u = fa[top[u]])
        (ret += query(1, 1, n, dfn[top[u]], dfn[u])) %= MOD;
    return (ret += MOD) %= MOD;
}
int main() {
    read(n), read(m);
    for (int i = 2, x; i <= n; i++)
        read(x), G[x+1].push_back(i);
    for (int i = 1, l, r, p; i <= m; i++)
        read(l), read(r), read(p), 
        opt[i*2-1].p = opt[i*2].p = p+1, 
        opt[i*2-1].id = opt[i*2].id = i, 
        opt[i*2-1].t = l, opt[i*2].t = r+1, 
        opt[i*2-1].f = false, opt[i*2].f = true;
    sort(opt+1, opt+m*2+1, cmp), DFS(1), DFS(1, 1);
    for (int i = 1, j = 0; i <= m*2; i++) {
        while (j < opt[i].t) change(++j);
        if (opt[i].f) (ans[opt[i].id] += getsum(opt[i].p)) %= MOD;
        else (ans[opt[i].id] += MOD-getsum(opt[i].p)) %= MOD;
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", (ans[i]%MOD+MOD)%MOD);
    return 0;
}