题解 P4175 【[CTSC2008]网络管理Network】
liuzhangfeiabc · · 题解
经典的带修树链第k大问题。
先说说几种道听途说的做法:
1、树剖+线段树套平衡树，查询时需要二分答案。
复杂度达到了惊人的4个log，更惊人的是据说妥妥能过。（实在懒得写写试试了qwq）
2、树剖+树状数组套主席树（或者树状数组套trie之类的），这样好处在于：主席树天生就可以直接求第k大而不用像平衡树那样二分答案。
（看似平衡树可以直接求第k大，实际上这样没法合并多棵平衡树的答案，必须得二分，而主席树不用。）
总之就是用树剖花1个log的代价把树上问题转化成序列问题，然后做法就多种多样了。
这样是3个log的，同样能过。
然后就是我写的做法：直接写树状数组套主席树。
前面几种做法都避不开树剖这一环，如果能省去这一步的话就能做到更优的复杂度。
考虑不带修的树链第k大，本质上就是查询4条链：根到u的答案+根到v的答案-根到lca的答案-根到lca父亲的答案。
所以我们可以像序列上那样建出前缀主席树，每个节点的主席树存储的是根到它路径上的所有点，然后同时查询4棵主席树就行了。
然而这样的话修改一个节点的权值会影响到它的子树内所有的节点，于是我们不得不暴力修改O（n）棵主席树。
不过既然一个点的修改只会对子树内的节点产生整体影响，我们可以考虑维护dfs序，因为一棵子树在dfs序上是一段连续的区间。
所以问题就变成了：dfs序上的区间修改，单点查询。这可以用树状数组实现。
具体操作是：把所有的主席树进行差分，差分后每棵主席树每个位置的值相当于原来它这个位置的值-原来它在dfs序上的前一棵主席树这个位置的值，这样可能会产生负数不过我们不用管。
修改时就是把区间修改转化成两个单点修改，查询时一次性查询4条链对应的前缀主席树。
于是这个题变成了两个log。
（不过据说这个题有1个log的神奇解法，不过我不会啊qwq）
上代码：
//ctsc2008 network:树上带修链上第k大
#include<bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pc putchar
#define f(i) st[0][i]
#define md int mid = l + r >> 1
#define ln t[q].ls,l,mid
#define rn t[q].rs,mid + 1,r
#define md int mid = l + r >> 1
int r(){
int x = 0;
char c;
c = gc;
while(!isdigit(c)) c = gc;
while(isdigit(c)){
x = (x << 1) + (x << 3) + c - '0';
c = gc;
}
return x;
}
void p(int q){
if(q >= 10) p(q / 10);
pc(q % 10 + '0');
}
int n,m;
struct edge{
int to,nxt;
}e[200010];
int fir[100010],cnt;
void ins(int u,int v){
e[++cnt].to = v;e[cnt].nxt = fir[u];fir[u] = cnt;
e[++cnt].to = u;e[cnt].nxt = fir[v];fir[v] = cnt;
}
struct qry{
int k,u,v;
}b[100010];
struct lsh{
int a,id;
bool bh;
}l[200010];
int ct,ct2,mx;
int dy[200010];
int fsts[100010],nxt[100010],dpt[100010],a[100010],st[20][100010];
int dfsx[100010],wz[100010],nw,sz[100010];
void dfs(int q){//打出dfs序
dfsx[++nw] = q;
wz[q] = nw;
sz[q] = 1;
for(int i = fir[q];i;i = e[i].nxt){
int j = e[i].to;
if(f(q) == j) continue;
f(j) = q;
nxt[j] = fsts[q];
fsts[q] = j;
dpt[j] = dpt[q] + 1;
dfs(j);
sz[q] += sz[j];
}
}
inline void buildst(){
for(register int i = 1;i <= 17;++i){
for(register int j = 1;j <= n;++j) st[i][j] = st[i - 1][st[i - 1][j]];
}
}
bool cp(lsh q,lsh w){
return q.a < w.a;
}
int lca(int u,int v){
if(dpt[u] < dpt[v]) swap(u,v);
int z = dpt[u] - dpt[v],i = 0;
while(z){
if(z & 1) u = st[i][u];
z >>= 1;
++i;
}
if(u == v) return u;
for(i = 17;i >= 0;--i){
if(st[i][u] == st[i][v]) continue;
u = st[i][u];
v = st[i][v];
}
return f(u);
}
int rt[100010];
struct tree{
int a,ls,rs;
}t[20000010];
void mdf(int &q,int l,int r,int x,int fx){//对一棵主席树进行修改
if(!q) q = ++ct;
t[q].a += fx;
if(l == r) return;
md;
if(x <= mid) mdf(ln,x,fx);
else mdf(rn,x,fx);
}
void xg(int q,int x,int fx){//一个单点修改操作
for(int i = q;i <= n;i += (i & -i)) mdf(rt[i],1,mx,x,fx);
}
int now[100010];
int ts[100010],ft;
bool vst[100010];
int cx(int u,int v,int w,int p,int x){//查询操作，注意4条链的贡献是u + v - w - p
int i;
ft = 0;
for(i = u;i;i -= (i & -i)) {
if(vst[i]) continue;
ts[++ft] = i;
vst[i] = 1;
}
for(i = v;i;i -= (i & -i)) {
if(vst[i]) continue;
ts[++ft] = i;
vst[i] = 1;
}
for(i = w;i;i -= (i & -i)) {
if(vst[i]) continue;
ts[++ft] = i;
vst[i] = 1;
}
for(i = p;i;i -= (i & -i)) {
if(vst[i]) continue;
ts[++ft] = i;
vst[i] = 1;
}//提前存一下4条链会经过的树状数组节点的集合便于处理
for(i = 1;i <= ft;++i) now[ts[i]] = rt[ts[i]];
int l = 1,r = mx,mid,as;
while(l < r){
mid = l + r >> 1;
as = 0;
for(i = u;i;i -= (i & -i)) as += t[t[now[i]].ls].a;
for(i = v;i;i -= (i & -i)) as += t[t[now[i]].ls].a;
for(i = w;i;i -= (i & -i)) as -= t[t[now[i]].ls].a;
for(i = p;i;i -= (i & -i)) as -= t[t[now[i]].ls].a;
if(as >= x){
for(i = 1;i <= ft;++i) now[ts[i]] = t[now[ts[i]]].ls;
r = mid;
}
else{
x -= as;
for(i = 1;i <= ft;++i) now[ts[i]] = t[now[ts[i]]].rs;
l = mid + 1;
}
}
for(i = 1;i <= ft;++i) vst[ts[i]] = 0;
return l;
}
void init(){//初始化
for(int i = 1;i <= n;++i){
xg(wz[i],a[i],1);
xg(wz[i] + sz[i],a[i],-1);
}
}
int main(){
int k,u,v,i,w;
n = r();
m = r();
for(i = 1;i <= n;++i) {
a[i] = r();
l[++ct2].a = a[i];
l[ct2]. bh = 0;
l[ct2].id = i;
}
for(i = 1;i < n;++i){
u = r();
v = r();
ins(u,v);
}
//以下是离散化部分，不过不离散化应该也行
for(i = 1;i <= m;++i){
b[i].k = r();
b[i].u = r();
b[i].v = r();
if(b[i].k) continue;
l[++ct2].a = b[i].v;
l[ct2].bh = 1;
l[ct2].id = i;
}
sort(l,l + ct2 + 1,cp);
l[0].a = -1;
for(i = 1;i <= ct2;++i){
if(l[i].a != l[i - 1].a) ++mx;
if(!l[i].bh) a[l[i].id] = mx;
else b[l[i].id].v = mx;
dy[mx] = l[i].a;
}
dfs(1);
buildst();
init();
for(i = 1;i <= m;++i){
u = b[i].u,v = b[i].v,k = b[i].k;
if(!k){
xg(wz[u],a[u],-1);
xg(wz[u] + sz[u],a[u],1);
a[u] = v;
xg(wz[u],a[u],1);
xg(wz[u] + sz[u],a[u],-1);
}
else{
w = lca(u,v);
k = dpt[u] + dpt[v] - 2 * dpt[w] - k + 2;//这里把第k大变成了第k小
if(k <= 0){
printf("invalid request!\n");
continue;
}
p(dy[cx(wz[u],wz[v],wz[w],wz[f(w)],k)]);
putchar('\n');
}
}
return 0;
}