P4211 [LNOI2014] LCA
大意
P4211 [LNOI2014] LCA
题目描述
有 \(m\) 次询问，每次询问给出 \(l, r, z\)，求 \(\sum_{i=l}^r dep[\operatorname{LCA}(i,z)]\) 。
思路
好题啊,首先我们想到一个很重要的问题，这个东西在 \(z\) 固定的情况下，其实与 \(l, r\) 并没有太大的关系，我们是可以差分处理的，直接计算 \(\sum_{i = 0} ^ {r} dep[\operatorname{LCA}(i, z)] - \sum_{i = 0} ^ {l - 1} dep[\operatorname{LCA}(i, z)]\)。
但是这样还是复杂度爆炸，我们需要进一步优化，考虑扫描线，我们如果直接把每次的询问 \([l, r]\) 划分为两个事件 \(l - 1\) 和 \(r\) ，这样一来，我们将这 \(m\) 个事件拆分为 \(2m\) 个事件，我们把这些事件按拆分出来的 pos 排序，然后按顺序处理这些询问，注意记录是 \(l - 1\) 还是 \(r\)，这两种的符号是不一样的。
代码
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100000 + 10;
const int MOD = 201314;
vector<int> g[N];
int n, m;
int par[N], son[N], sz[N], dep[N];
int top[N], dfn[N], who[N], CLOCK;#define lc (rt << 1)
#define rc (rt << 1 | 1)void pre(int u, int p, int d){par[u] = p, son[u] = -1, sz[u] = 1, dep[u] = d;int mx = 0;for(int i = 0;i < g[u].size();i ++){int v = g[u][i];if(p == v) continue;pre(v, u, d + 1);sz[u] += sz[v];if(sz[v] > mx){mx = sz[v], son[u] = v;}}
}void dfs(int u, int p){top[u] = p, dfn[u] = ++ CLOCK;if(son[u] != -1){dfs(son[u], p);}for(int i = 0;i < g[u].size();i ++){int v = g[u][i];if(v == son[u] || v == par[u]){continue;}dfs(v, v);}
}int sum[N << 2], lz[N << 2];
void pushdown(int rt, int l, int r){if(lz[rt]){int mid = (l + r) >> 1;lz[lc] = (lz[lc] + lz[rt]) % MOD;sum[lc] = (sum[lc] + (mid - l + 1LL) * lz[rt]) % MOD;lz[rc] = (lz[rc] + lz[rt]) % MOD;sum[rc] = (sum[rc] + (r - mid + 0LL) * lz[rt]) % MOD;lz[rt] = 0;}
}void update(int l, int r, int rt, int L, int R, int x){if(L <= l && r <= R){lz[rt] = (lz[rt] + x) % MOD;sum[rt] = (sum[rt] + (r - l + 1LL) * x) % MOD;return;}int mid = (l + r) >> 1;pushdown(rt, l, r);if(L <= mid) update(l, mid, lc, L, R, x);if(R > mid) update(mid + 1, r, rc, L, R, x);sum[rt] = (sum[lc] + sum[rc]) % MOD;
}int query(int l, int r, int rt, int L, int R){if(L <= l && r <= R){return sum[rt];}int mid = (l + r) >> 1, ans = 0;pushdown(rt, l, r);if(L <= mid){ans = (ans + query(l, mid, lc, L, R)) % MOD;}if(R > mid){ans = (ans + query(mid + 1, r, rc, L, R)) % MOD;}return ans;
}void pathC(int u, int x){int v = 0;while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]]) swap(u, v);update(1, n, 1, dfn[top[u]], dfn[u], x);u = par[top[u]];}if(dep[u] > dep[v]) swap(u, v);update(1, n, 1, dfn[u], dfn[v], x);
}int pathS(int u){int v = 0, ans = 0;while(top[u] != top[v]){if(dep[top[u]] < dep[top[v]]) swap(u, v);ans = (ans + query(1, n, 1, dfn[top[u]], dfn[u])) % MOD;u = par[top[u]];}if(dep[u] > dep[v]) swap(u, v);ans = (ans + query(1, n, 1, dfn[u], dfn[v])) % MOD;return ans;
}struct node{int pos, z, id, sign;bool operator < (const node &b)const{return pos < b.pos;}
}q[N << 1];
int Ans[N];int main(){scanf("%d%d", &n, &m);for(int i = 1;i < n;i ++){int p; scanf("%d", &p);g[p].push_back(i);}pre(0, 0, 1);dfs(0, 0);int cnt = 0;for(int i = 1;i <= m;i ++){int l, r, z; scanf("%d%d%d", &l, &r, &z);q[++ cnt] = {l - 1, z, i, -1};q[++ cnt] = {r, z, i, 1};}sort(q + 1, q + cnt + 1);int cur = -1;for(int i = 1;i <= cnt;i ++){while(cur < q[i].pos){pathC(++ cur, 1);}int res = pathS(q[i].z);if(q[i].sign == 1) Ans[q[i].id] = (Ans[q[i].id] + res) % MOD;else Ans[q[i].id] = (Ans[q[i].id] - res + MOD) % MOD;}for(int i = 1;i <= m;i ++){printf("%d\n", Ans[i]);}return 0;
}