題解[P7357 中位數]

題目連結

我不會告訴你我是因為題目背景的頭像與我們班主任一毛一樣才來寫題解的

題意：

給出一棵樹，點有點權，每次将一個點的點權異或 \(1\) ，

或給出兩個點 \(u,v\) ，詢問能覆寫 \(u,v\) 的路徑所形成的序列的中位數最大值。

保證這 \(u,v\) 不在一條鍊上，這裡中位數指長為 \(n\) 的序列中第 \(\left\lfloor\frac{n+1}{2}\right\rfloor\) 大的數。

\(\text{Step 1}\)

先看一下這種定義下的中位數的性質：

對于一個序列 \(S,n=\left|S\right|\)

設 \(g_a=|\{i|s_i\geq a,1\leq i\leq n\}|,l_a=|\{i|s_i< a,1\leq i\leq n\}|\)

則 \(S\) 的中位數就是原序列中滿足 \(g_a\leq l_a\) 的最大的 \(a\)

如果把 \(\geq a\) 的數設為 \(1\) ，把 \(<a\) 的數設為 \(-1\) ，\(a\) 是中位數時必須這些 \(1\) 與 \(-1\) 的和 \(\geq 0\) ，且 \(a\) 最大。

由于設成 \(1\) 與 \(-1\) 的操作在 \(a\) 遞增時 \(-1\) 增多，可以建出一顆主席樹來維護。

這套路在 此題 中曾出現過。

\(\text{Step 2}\)

對于題目中的滿足覆寫 \(u,v\) 的路徑的中位數最大值，是有單調性的，考慮二分。

對于一個二分的值 \(mid\) 我們希望得知：把樹上每個點權 \(\geq mid\) 的點的 鍵值 設成 \(1\) ，把點權 \(<mid\) 的點的鍵值 設成 \(-1\) 後，檢視能覆寫 \(u,v\) 路徑中 鍵值的和的最大值 能否 \(\geq 0\) 。

由于要覆寫 \(u,v\) 且 \(u,v\) 不在一條路徑上，考慮樹上差分。

設 \(f_x^a=\text{a時x到根路徑鍵值之和}\)

是以二分時要求的鍵值的和的最大值就是：

\(\max\limits_{x\in \operatorname{subtree}(u)}f_x^{mid}+\max\limits_{y\in \operatorname{subtree}(v)}f_y^{mid}-2f_{\operatorname{lca}(u,v)}^{mid}+w_{\operatorname{lca}(u,v)}^{mid}\)

其中 \(w_x^{a}\) 代表 \(a\) 時 \(x\) 的鍵值。

于是希望對每個 \(a\) 維護 \(dfs\) 序所代表的點的 \(f_x^a\) 值，這樣就容易查詢子樹最大值。

\(\text{Step 3}\)

考慮如何用主席樹維護 \(f_x^a\) 值。

對于 \(a=0\) 時，\(f_x^a=\operatorname{dep}(x)\) ，即 \(x\) 的深度，因為所有點的點權 \(\geq 0\) 。

當 \(a\) 變大時會導緻一些點的鍵值從 \(1\) 變成 \(-1\)

那這些點的子樹内的所有點的 \(f^a\) 值就會 \(-2\) 。

由于主席樹是以 \(dfs\) 序為下标建的，這相當于區間減并可持久化。

這可以用 标記永久化 輕松實作。

\(\text{Step 4}\)

現在隻剩下最後一個問題：把點權異或 \(1\)

開始建主席樹時順便把每個點的點權異或 \(1\) 後的值順帶着離散化并建主席樹。

由于異或 \(1\) 後一個點的點權要麼變大一，要麼減小一。

設 \(t_x=2\left\lfloor\frac{x}{2}\right\rfloor+1\) ，即不比 \(x\) 小的最小的奇數。

那麼 \(a>t_x\) 的版本無論如何都不發生改變，因為\(\max(x,x\operatorname{xor}1)\leq t_x\)

而 \(a\leq t_x-1\) 的版本同樣不發生變化，因為 \(\min(x,x\operatorname{xor}1)\geq t_x-1\)

是以受改動的版本僅有 \(t_x\) 一個。

若 \(x\) 為奇數， \(t_x=x\) , 異或後變小成 \(x-1\) 。

那原先 \(x\) 的版本中這個點的鍵值為 \(1\) ，權值變小後要成為 \(-1\)

是以将 \(x\) 的版本中這個點的子樹内所有點的 \(f\) 值 \(-2\)

若 \(x\) 為偶數， \(t_x=x+1\) ，異或後變大成 \(x+1\)

那原先 \(x+1\) 的版本中這個點的鍵值為 \(-1\) ，權值變大後要成為 \(1\)

是以将 \(x+1\) 的版本中這個點的子樹内所有點的 \(f\) 值 \(+2\)

這同樣可用标記永久化實作。

\(\text{Step 5}\)

代碼：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,nn,x,y,opt,tot,tt,l,L,R,mid,cnt,qx,qy;
int a[N],b[N],rt[N],ii[N];
int dfn[N],rev[N],sz[N],dep[N],f[N][20];
int to[N],nextn[N],h[N],edg;char ch;
inline void add(int x,int y){to[++edg]=y,nextn[edg]=h[x],h[x]=edg;}
#define id(x) lower_bound(b+1,b+nn+1,x)-b
struct tree{int l,r,tag,mx;}t[N<<5];
inline void read(int &x){
	x=0;ch=getchar();while(ch<48||ch>57)ch=getchar();
	while(ch>47&&ch<58)x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
void write(int x){if(x>9)write(x/10);putchar(48+x%10);}
void build(int &k,int l,int r){
	k=++tot;
	if(l^r){
		int mid=(l+r)>>1;
		build(t[k].l,l,mid);build(t[k].r,mid+1,r);
		t[k].mx=max(t[t[k].l].mx,t[t[k].r].mx);
	}
	else t[k].mx=dep[rev[l]];
}
void update(int &k,int kk,int l,int r,int x,int y,int v){
	k=++tot;t[k]=t[kk];
	if(x<=l&r<=y)t[k].tag+=v,t[k].mx+=v;
	else {
		int mid=(l+r)>>1;
		if(x<=mid)update(t[k].l,t[kk].l,l,mid,x,y,v);
		if(mid<y)update(t[k].r,t[kk].r,mid+1,r,x,y,v);
		t[k].mx=max(t[t[k].l].mx,t[t[k].r].mx)+t[k].tag;
	}
}
int inquiry(int k,int l,int r,int pos){
	if(l^r){
		int mid=(l+r)>>1;
		if(pos<=mid)return inquiry(t[k].l,l,mid,pos)+t[k].tag;
		else return inquiry(t[k].r,mid+1,r,pos)+t[k].tag;
	}
	else return t[k].mx;
}
int inquiry_mx(int k,int l,int r,int x,int y){
	if(x<=l&&r<=y)return t[k].mx;
	int mid=(l+r)>>1;
	if(x<=mid&&mid<y)
		return max(inquiry_mx(t[k].l,l,mid,x,y),inquiry_mx(t[k].r,mid+1,r,x,y))+t[k].tag;
	else if(x<=mid)return inquiry_mx(t[k].l,l,mid,x,y)+t[k].tag;
	else return inquiry_mx(t[k].r,mid+1,r,x,y)+t[k].tag;
}
void init(int x,int anc){
	int i,y;rev[dfn[x]=++tt]=x;
	sz[x]=1;dep[x]=dep[anc]+1;f[x][0]=anc;
	for(i=1;i^20;++i)f[x][i]=f[f[x][i-1]][i-1];
	for(i=h[x];y=to[i],i;i=nextn[i])if(y^anc)init(y,x),sz[x]+=sz[y];
	h[x]=0;
}
int lca(int x,int y){
	int i;if(dep[x]<dep[y])x^=y^=x^=y;
	for(i=19;~i;--i)if(dep[f[x][i]]>=dep[y])x=f[x][i];
	if(x==y)return x;
	for(i=19;~i;--i)if(f[x][i]^f[y][i])x=f[x][i],y=f[y][i];
	return f[x][0];
}
main(){
	read(n);read(m);register int i,j;
	for(i=1;i<=n;++i){read(a[i]),b[++nn]=a[i];if(a[i]^1)b[++nn]=a[i]^1;}
	sort(b+1,b+nn+1);nn=unique(b+1,b+nn+1)-b-1;
	for(i=1;i^n;++i)read(x),read(y),add(x,y),add(y,x);
	init(1,0);edg=0;build(rt[0],1,n);
	for(i=1;i<=n;++i)add(ii[i]=id(a[i]),i),ii[i]+=(a[i]&1)^1;
	for(i=1;rt[i]=rt[i-1],i<=nn;++i)for(j=h[i-1];x=to[j],j;j=nextn[j])
		update(rt[i],rt[i],1,n,dfn[x],dfn[x]+sz[x]-1,-2);
	while(m--){
		read(opt);read(x);
		if(opt==1){
			i=ii[x];
			if(a[x]&1)update(rt[i],rt[i],1,n,dfn[x],dfn[x]+sz[x]-1,-2);
			else update(rt[i],rt[i],1,n,dfn[x],dfn[x]+sz[x]-1,2);
			a[x]^=1;
		}
		else {
			read(y);l=lca(x,y);
			L=0;R=nn;
			while(L<R){
				mid=L+R+1>>1;cnt=0;
				cnt+=inquiry_mx(rt[mid],1,n,dfn[x],dfn[x]+sz[x]-1);
				cnt+=inquiry_mx(rt[mid],1,n,dfn[y],dfn[y]+sz[y]-1);
				cnt-=(inquiry(rt[mid],1,n,dfn[l])<<1)+(a[l]>=b[mid]?-1:1);
				if(cnt>=0)L=mid;else R=mid-1;
			}
			write(b[L]);putchar('\n');
		}
	}
}