「SCOI2015」情报传递
题目描述
奈特公司是一个巨大的情报公司，它有着庞大的情报网络。情报网络*有 \(n\) 名情报员。每名情报员可能有若干名（可能没有）下线，除 \(1\) 名大头目外其余 \(n - 1\) 名情报员有且仅有 \(1\) 名上线。奈特公司纪律森严，每名情报员只能与自己的上、下线联系，同时，情报网络中仟意两名情报员一定能够通过情报网络传递情报。
奈特公司每天会派发以下两种任务中的一个任务：
- 搜集情报：指派 \(T\) 号情报员搜集情报；
- 传递情报：将一条情报从 \(X\) 号情报员传递给 \(Y\) 号情报员。
情报员最初处于潜伏阶段，他们是相对安全的，我们认为此时所有情报员的危险值为 \(0\)；一旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加 \(1\) 点危险值。传递情报并不会使情报员的危险值增加。
为了保证传递情报的过程相对安全，每条情报都有一个风险控制值 \(C\)。余特公司认为，参与传递这条情报的所有情报员中，危险值大于 \(C\) 的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。
\(n≤2×10^5,Q≤2×10^5,0<P_i,C_i≤N,1≤T_i,X_i,Y_i≤n\)
解题思路 :
观察发现，只有在第 $ i-C_i-1$ 天之前搜集情报的节点才可能对答案产生贡献
那么问题就转化为点权 $+1 $，和求某一时刻树上一条链上的点权和
比较简单的做法就是将询问离线下来树链剖分即可，复杂度是 $O(nlog^2n) $，而且不能做强制在线
考虑到询问某一时刻其实就是访问历史版本，那么只需要对树上的点权信息进行可持久化即可
记 \(sum_i\) 表示某一时刻 \(i\) 到 \(root\) 的路径的点权和，那么答案就是 \(sum_x + sum_y - sum_{lca} - sum_{fa(lca)}\)
也就是说只要对 \(sum\) 数组可持久化就好了，显然每一次新建一个版本时一个子树的点权都会 \(+1\) ，这东西在 \(dfn\) 序上是一段连续的区间，直接 \(ins\) 即可，总复杂度是 $O(nlogn) $
/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int f = 0, ch = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
#define fi first
#define se second
const int N = 200005;
vector<int> g[N];
int rt[N], sz[N], ds[N], dep[N], dfn[N], f[N][21], vis[N], n, m, cnt, root;
namespace Prework{
inline void dfs(int u, int fa){
sz[u] = 1, f[u][0] = fa, dep[u] = dep[fa] + 1, dfn[u] = ++cnt;
for(int i = 0; i < g[u].size(); i++)
if(g[u][i] != fa) dfs(g[u][i], u), sz[u] += sz[g[u][i]];
}
inline void realmain(){
dfs(root, 0);
for(int j = 1; j <= 20; j++)
for(int i = 1; i <= n; i++) f[i][j] = f[f[i][j-1]][j-1];
}
}
inline pair<int, int> Getpath(int x, int y){
if(dep[x] < dep[y]) swap(x, y);
for(int i = 20; ~i; i--){
if(dep[f[x][i]] >= dep[y]) x = f[x][i];
if(dep[x] == dep[y]) break;
}
if(x == y) return make_pair(x, f[x][0]);
for(int i = 20; ~i; i--)
if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return make_pair(f[x][0], f[f[x][0]][0]);
}
struct SegmentTree{
struct Node{ int lc, rc, add; } T[N*50]; int size;
inline void ins(int &u, int pr, int l, int r, int L, int R){
T[u=++size] = T[pr];
if(l >= L && r <= R) return (void) (T[u].add++);
int mid = l + r >> 1;
if(L <= mid) ins(T[u].lc, T[pr].lc, l, mid, L, R);
if(mid < R) ins(T[u].rc, T[pr].rc, mid + 1, r, L, R);
}
inline int query(int u, int l, int r, int pos){
if(l == r) return T[u].add;
int mid = l + r >> 1, res = 0;
if(pos <= mid) res += query(T[u].lc, l, mid, pos);
else res += query(T[u].rc, mid + 1, r, pos);
return res + T[u].add;
}
}van;
inline int calc(int x, int y){
if(!dfn[y] || !ds[x]) return 0;
return van.query(rt[ds[x]], 1, n, dfn[y]);
}
int main(){
read(n);
for(int i = 1, x; i <= n; i++){
read(x);
if(x) g[x].push_back(i), g[i].push_back(x); else root = i;
}
Prework::realmain();
read(m);
for(int i = 1, op, x, y, z; i <= m; i++){
read(op), read(x);
if(op == 1){
ds[i] = ds[i-1], read(y), read(z); int t = Max(i - z - 1, 0);
pair<int, int> now = Getpath(x, y);
int res = calc(t, x) + calc(t, y) - calc(t, now.fi) - calc(t, now.se);
printf("%d %d\n", dep[x] + dep[y] - dep[now.fi] - dep[now.se], res);
}
else{
if(vis[x]){ ds[i] = ds[i-1]; continue; }
ds[i] = ds[i-1] + 1, vis[x] = 1;
van.ins(rt[ds[i]], rt[ds[i-1]], 1, n, dfn[x], dfn[x] + sz[x] - 1);
}
}
return 0;
}