动态链上第k小——整体二分+ds：P4175

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135253442

https://www.luogu.com.cn/problem/P4175

第k大先转第k小。

考虑离线。离线完后此题采用整体二分，对于当前二分区间是独立的。把所以操作的查询按时间戳排序。

对于修改操作，如果当前点上的值小于等于mid，则可以有贡献。

对于查询操作，要判断当前两点链上有多少个点有权值。可以用树上差分来解决，所以上一步的维护就要支持子树加，所以转dfs序就是区间加单点求值，树状数组可维护。

如果当前有点的权值数量太多，说明答案小于等于mid，那就丢到左边去二分。如果太少，说明答案大于mid，那么久先减去当前二分区间的贡献， 再丢到右边。

1
2
3
4
5
pre coding at 14:26
st coding at 16:21
st bugging at 18:21
passing at 18:51
fn blogging at 19:00
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCALd
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//srand(time(0));
#define N 80010
//#define M
//#define mo
struct node {
	int op, x, y, t, k; 
};
vector<node>s;  
int n, m, i, j, k, T;
int ans[N], f[N][22], L[N], R[N], dfn[N], dep[N]; 
int tot, q, u, v, a[N], x, y, len; 
vector<int>G[N]; 

void dfs(int x, int fa) {
	dep[x]=dep[fa]+1; f[x][0]=fa; 
	dfn[x]=L[x]=++tot; 
	for(int y : G[x]) {
		if(y == fa) continue; 
		dfs(y, x); 
	}
	R[x]=tot; 
}

int lca(int x, int y) {
	if(x==y) return x; 
	if(dep[x] < dep[y]) swap(x, y); 
	for(int k=20; k>=0; --k)
		if(dep[f[x][k]]>=dep[y]) x=f[x][k]; 
	if(x==y) return x; 
	for(int k=20; k>=0; --k) 
		if(f[x][k] != f[y][k]) x=f[x][k], y=f[y][k]; 
	return f[x][0]; 
}

struct Binary_tree {
	int cnt[N]; 
	void add(int x, int k) {
		while(x<N) cnt[x]+=k, x+=x&-x; 
	}
	int que(int x) {
		int ans=0; 
		while(x) ans+=cnt[x], x-=x&-x; 
		return ans; 
	}
	int calc(int x, int y) {
		int z = lca(x, y); 
//		debug("calc(%d %d) => %d | %d %d %d %d\n", x, y, que(dfn[x])+que(dfn[y])-que()-que(f[z][0]), que(dfn[x]), que(dfn[y]), qye(z), ); 
		return que(dfn[x])+que(dfn[y])-que(dfn[z])-que(dfn[f[z][0]]); 
	}
	void add(int l, int r, int k) {
		add(l, k); add(r+1, -k); 
	}
}Bin;

void solve(int l, int r, vector<node>s) {
	if(l==r) {
		for(auto t : s) if(t.op==2) ans[t.t]=l; 
		return ; 
	}
	int mid = (l + r) >> 1; 
	auto cmp = [&] (node x, node y) -> bool {
		if(x.t == y.t) return x.op < y.op; 
		return x.t < y.t; 
	}; 	
	sort(s.begin(), s.end(), cmp); 
	debug("######$$####### [%d %d] mid %d\n", l, r, mid); 
//	for(auto t : s) debug("%d(op) %d(x) %d(y) %d(t) %d(k)\n", t.op, t.x, t.y, t.t, t.k); 
	int x, k; 
	vector<node>va, vb; 
	for(auto t : s) {
		debug("%d(op) %d(x) %d(y) %d(t) %d(k)\n", t.op, t.x, t.y, t.t, t.k); 
		if(t.op==1) {
			if(t.y <= mid) {
				va.pb(t); x=t.x; 
				debug("Add[%d %d] %d\n", L[x], R[x], x); 
				Bin.add(L[x], R[x], t.k);
			}
			else vb.pb(t); 
		}
		else {
			k = Bin.calc(t.x, t.y); 
			if(k >= t.k) va.pb(t); 
			else t.k-=k, vb.pb(t); 
		}
	}
	for(auto t : va) if(t.op==1) Bin.add(L[t.x], R[t.x], -t.k); 
	if(!va.empty()) solve(l, mid, va); 
	if(!vb.empty()) solve(mid+1, r, vb); 
} 

signed main() {
	#ifdef LOCALs
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	T=read();
//	while(T--) {
//
//	}
	n=read(); q=read(); 
	for(i=1; i<=n; ++i) { a[i]=read(); s.pb({1, i, a[i], 1, 1}); }
	for(i=1; i<n; ++i) { u=read(); v=read(); G[u].pb(v); G[v].pb(u); }
	dfs(1, 0); 
	for(k=1; k<=20; ++k) for(i=1; i<=n; ++i) f[i][k]=f[f[i][k-1]][k-1]; 
	debug("dep : "); for(i=1; i<=n; ++i) debug("%d ", dep[i]); debug("\n"); 
	for(i=1; i<=q; ++i) {
		k=read(); x=read(); y=read(); 
		if(k==0) {
			s.pb({1, x, a[x], i, -1}); 
			a[x]=y; 
			s.pb({1, x, a[x], i, 1}); 
		}
		else {
			len=dep[x]+dep[y]-2*dep[lca(x, y)]+1; 
//			debug("Len (%d <-> %d) %d\n", x, y, len); 
			debug("%d %d | %d\n", x, y, len-k+1); 
			if(k > len) ans[i] = -1; 
			else s.pb({2, x, y, i, len-k+1}); 
		}
	}
//	solve(1, 10, s); 
	solve(1, 1e8, s); 
	for(i=1; i<=q; ++i) 
		if(!ans[i]) continue; 
		else if(ans[i]==-1) printf("invalid request!\n"); 
		else printf("%d\n", ans[i]); 
	return 0;
}