FJ的农场 题解

原题见P4216
首先 \(\Theta(mn)\) 暴力能够拿到 \(30\) 分，这个没有什么难度，可以参照一下我用来测试的暴力Link。

首先让我们来简化一下题意：

• 插入操作（即 "\(Grow\)" ），将树上某个点的值赋值为 \(Val_i\) 。
• 查询操作（即 "\(Walk\)" ），给定一个值（即操作的编号）\(Val\)，查询树上 \(S_i\) 到 \(E_i\) 的路径上有多少个点以及有多少个点满足 \(Val - Val_x > L_i\)

题解区有很多写树链剖分套主席树的在线算法，时间复杂度为 \(\Theta(n log^3 n)\)。代码比较难写，而且复杂度没有我用的方法优，因此我就不讲了，想看的可以到原题题解区看看。

这里提供一个离线算法：
我们对于任何一个查询（ \(S_i\) , \(E_i\) , \(L_i\) ，当前时间为 \(t\) ），我们要查询这个路径上满足 \(t - Val_x > L_i\) 的点的数量，我们对这个式子进行移项，得到 \(t - L_i > Val_x\) ，等价于 \(t - L_i - 1 \ge Val_x\) 。然后我们知道其实 \(Val_x\) 也是时间的编号 \(t_x\)。因此我们可以根据时间的时间编号进行排序。查询操作的时间就是 \(T_i\) ，修改操作的时间就是 \(T_i - L_i - 1\)。排序完之后再进行操作，就是树剖板题了。

Code:

#include<bits/stdc++.h>
#define M 200100
using namespace std;
inline int read(){
	int w = 1, s = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-')w = -w;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		s = (s<<3) + (s<<1) + (ch^48);
		ch = getchar();
	}
	return w * s;
}
struct Q{
	int x, y, c, tim, opt, uid;
}a[M];
struct Node{
	int l, r, sum;
}node[M << 2];
int n, q, root, fa[M], depth[M], size[M], son[M], top[M], id[M], cnt, tot, num, print_tot[M], print_x[M];
vector<int>to[M];
bool cmp(Q x, Q y){
	return (x.tim == y.tim) ? (x.opt > y.opt) : (x.tim < y.tim);
}
void pushup(int u){
	node[u].sum = node[u << 1].sum + node[u << 1 | 1].sum;
	return ;
}
void build(int u, int l, int r){
	node[u] = (Node){l, r};
	if(l == r) return ;
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	return ;
}
void Update(int u, int pos){
	if(node[u].l == node[u].r){
		node[u].sum ++;
		return ;
	}
	int mid = node[u].l + node[u].r >> 1;
	if(pos <= mid) Update(u << 1, pos);
	else Update(u << 1 | 1, pos);
	pushup(u);
	return ;
}
void dfs1(int x, int dep){
	depth[x] = dep; size[x] = 1;
	int maxn = 0;
	for(int i = 0; i < to[x].size(); i++){
		dfs1(to[x][i], dep + 1);
		size[x] += size[to[x][i]];
		if(maxn < size[to[x][i]]){
			maxn = size[to[x][i]];
			son[x] = to[x][i];
		}
	}
	return ;
}
void dfs2(int x, int topf){
	top[x] = topf; id[x] = ++cnt;
	if(son[x]) dfs2(son[x], topf);
	for(int i = 0; i < to[x].size(); i++)
	 if(to[x][i] != son[x])
	  dfs2(to[x][i], to[x][i]);
	return ;
}
int query(int u, int l, int r){
	if(l <= node[u].l && node[u].r <= r) return node[u].sum;
	int mid = node[u].l + node[u].r >> 1, ans = 0;
	if(l <= mid) ans = query(u << 1, l, r);
	if(mid < r) ans += query(u << 1 | 1, l, r);
	return ans;
}
int find(int x, int y){
	int ans = 0;
	while(top[x] != top[y]){
		if(depth[top[x]] < depth[top[y]]) swap(x, y);
		ans += query(1, id[top[x]], id[x]); tot += id[x] - id[top[x]] + 1;
		x = fa[top[x]];
	}
	if(depth[x] < depth[y]) swap(x, y);
	ans += query(1, id[y], id[x]); tot += id[x] - id[y] + 1;
	return ans;
}
int main(){
	n = read();
	for(int i = 1; i <= n; i++){
		fa[i] = read();
		if(fa[i] == 0) root = i;
		else to[fa[i]].push_back(i);
	}
	q = read();
	for(int i = 1; i <= q; i++){
		int opt = read(); a[i].opt = opt;
		if(opt == 1) a[i].x = read(), a[i].y = read(), a[i].c = read(), a[i].tim = i - a[i].c - 1, a[i].uid = ++ num;
		else a[i].x = read(), a[i].tim = i;
	}
	sort(a + 1, a + q + 1, cmp);
	dfs1(root, 1);
	dfs2(root, root);
	build(1, 1, n);
	int x;
	for(int i = 1; i <= q; i++)
	 if(a[i].opt == 2) Update(1, id[a[i].x]);
	 else tot = 0, print_x[a[i].uid] = find(a[i].x, a[i].y), print_tot[a[i].uid] = tot;
	for(int i = 1; i <= num; i++)
	 printf("%d %d\n", print_tot[i], print_x[i]);
	return 0;
}