自动搬运

查看原文

来自洛谷，原作者为

	_QAQ 人生赢家，迷妹请加我QQ：2767553551

搬运于2025-08-24 22:12:18，当前版本为作者最后更新于2019-10-14 23:15:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

结合了最小割，贪心，甚至还有点模拟费用流的贪心思想(((

首先有最小割模型，将所有 $(i,j)$有 $e_i \oplus e_j \geq k$ 的点对连边作最小割。

对应到 $\operatorname{Trie}$ 上的 $2$ 个节点 $x,y$，如何计算其子树内的点连边后得到的最小割。

注意到最小割即为网络流，若 $k$ 当前位权值为 $1$，意味着 $x_0$ 与 $y_0$ 无法匹配，$x_1$ 与 $y_1$ 无法匹配。

否则，若当前位权值为 $0$，意味着 $x_0$ 与 $y_1$ 一定能完全匹配，$x_1$ 与 $y_0$ 一定能完全匹配。

若 $|x_0|<|y_1|,|x_1|<|y_0|$，则答案为 $|x_0|+|x_1|$

若 $|y_0|<|x_1|,|y_1|<|x_0|$，则答案为 $|y_0|+|y_1|$

否则，以 $|x_0|<|y_1|,|x_1|>|y_0|$ 为例，答案显然为$\min(\operatorname{merge(x_1,y_1)},|y_1|-|x_0|,|x_1|-|y_0|)+|x_0|+|y_0|$

注意到修改时只会修改 $\log n$ 个节点的权值，类似记搜防止递归计算，保证复杂度。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7,M=1e7+7; bool fl[M];
int n,q,tot,dep[M],siz[M],ans[M],ch[M][2];
long long k,w[N];
inline long long read(){
	long long num=0; char g=getchar(); while(g<48||57<g) g=getchar();
	while(47<g&&g<58) num=(num<<1)+(num<<3)+g-48,g=getchar(); return num;
}
inline void write(int u){
	if(u>9) write(u/10); putchar(u%10+'0');
}
inline void ins(int u,long long k){
	siz[u]++,fl[u]=0; if(dep[u]<0) return;
	if(k&(1ll<<dep[u])){
		if(!ch[u][1]) ch[u][1]=++tot,dep[tot]=dep[u]-1; ins(ch[u][1],k);
	}
	else{
		if(!ch[u][0]) ch[u][0]=++tot,dep[tot]=dep[u]-1; ins(ch[u][0],k);
	}
}
inline void del(int u,long long k){
	siz[u]--,fl[u]=0; if(dep[u]<0) return;
	if(k&(1ll<<dep[u])) del(ch[u][1],k); else del(ch[u][0],k);
}
inline int getans(int u,int v){
	if(!siz[u]||!siz[v]) return 0;
	
	if(dep[u]<0){
		if(u==v) return ans[u]=siz[u]-(siz[u]&1); return ans[u]=min(siz[u],siz[v]);
	}
	if(fl[u]&&fl[v]) return ans[u]; fl[u]=1,fl[v]=1;
	if(k&(1ll<<dep[u])){
		if(u==v) ans[u]=ans[v]=getans(ch[u][0],ch[v][1]);
		else ans[u]=ans[v]=getans(ch[u][0],ch[v][1])+getans(ch[u][1],ch[v][0]);
		return ans[u];
	}
	else{
		int fq=getans(ch[u][0],ch[v][0]),fw=getans(ch[u][1],ch[v][1]);
		if(u==v) ans[u]=fq+fw+min(siz[ch[u][0]]-fq,siz[ch[v][1]]-fw);
		else if(siz[ch[u][0]]<=siz[ch[v][1]]&&siz[ch[u][1]]<=siz[ch[v][0]]) ans[u]=siz[ch[u][0]]+siz[ch[u][1]];
		else if(siz[ch[u][0]]>=siz[ch[v][1]]&&siz[ch[u][1]]>=siz[ch[v][0]]) ans[u]=siz[ch[v][0]]+siz[ch[v][1]];
		else if(siz[ch[u][0]]<=siz[ch[v][1]]&&siz[ch[u][1]]>=siz[ch[v][0]]){
			fw=min(min(fw,siz[ch[v][1]]-siz[ch[u][0]]),siz[ch[u][1]]-siz[ch[v][0]]);
			ans[u]=fw+siz[ch[u][0]]+siz[ch[v][0]];
		}
		else{
			fq=min(min(fq,siz[ch[v][0]]-siz[ch[u][1]]),siz[ch[u][0]]-siz[ch[v][1]]);
			ans[u]=fq+siz[ch[u][1]]+siz[ch[v][1]];
		}
		ans[v]=ans[u]; return ans[u];
	}
}
int main(){
	n=read(),q=read(),k=read(),dep[1]=60,tot=1; int c;
	for(int i=1;i<=n;i++) w[i]=read(),ins(1,w[i]);
	write(max(n-getans(1,1),1)),putchar('\n');
	for(int i=1;i<=q;i++)
		c=read(),del(1,w[c]),w[c]=read(),ins(1,w[c]),write(max(n-getans(1,1),1)),putchar('\n');
	return 0;
}