自动搬运

查看原文

来自洛谷，原作者为

	Y_B_X ...

搬运于2025-08-24 22:12:06，当前版本为作者最后更新于2021-11-11 22:38:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目链接

题意:
给定一张完全图，每两个点 $(i,j)$ 之间有三种边 $A_{(i,j)},B_{(i,j)},C_{(i,j)}$ 。
其中 $A_{(i,j)}=a_i\operatorname{xor} a_j,B{(i,j)}=b_i\operatorname{xor} b_j,C_{(i,j)}=c_i\operatorname{xor} c_j$。
每次查询对三种边分别给出一个起点与阀值，
问从三种图中分别从各自起点开始，经过不大于各自阀值的边到达的点的交集。

这道题几乎是强行拼题。

首先对每张图求出各自的 $\text{Kruskal}$ 重构树，就是这题。

从大到小枚举每一位，将这一位为 $0,1$ 的分开考虑，建出将两边各自的 $\text{Kruskal}$ 重构树，然后用 $\text{01trie}$ 查询两边 $\operatorname{xor}$ 得到的最小值，得到当前这层的 $\text{Kruskal}$ 重构树。

正确性是因为每次让大的位出现得尽量小，使位数更低的妥协，而 $2\times 2^{d-1}\leq 2^d$，得到的一定是最优方案之一。

每个点会被查询至多 $\log V$ 次，每次 $\text{01trie}$ 上的点查询需要 $O(\log V)$，这部分总时间为 $O(n\log^2V)$。

注意这样将相同的数分到一份时异或为 $0$，也要建出其重构树。

这之后每次查询就能在 $\text{Kruskal}$ 重构树上，倍增得到能到达的点集所在的 $dfn$ 序范围。

设 $A,B,C$ 三图各自 $dfn$ 序范围是 $[la,ra],[lb,rb],[lc,rc]$。

那查询转为询问满足 $\begin{cases}la\leq dfna_i\leq ra\\lb\leq dfnb_i\leq rb\\lc\leq dfnc_i\leq rc\end{cases}$ 的 $i$ 的个数。

这就是个明显的三维偏序，可以通过三维差分拆成八个询问后，一个 $\text{cdq}$ 分治轻松解决。

这部分时间复杂度为 $O(m\log m\log n)$。

总时间复杂度为 $O(n\log^2V+m\log n\log m)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,K=28;
const int inf=2e8;
int n,m,x,y,nn,tt,v,tot;char ch;
int a[N][3],son[N][2][3],w[N][3];
struct trie{int son[2],sz;}_[N*K];
int _rt,_tot,_v;bool _b;
inline void read(int &x){
	x=0;ch=getchar();while(ch<48)ch=getchar();
	while(ch>47)x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
void write(int x){if(x>9)write(x/10);putchar(48+x%10);}
void update(int &k,int x,int i){
	if(!k)k=++_tot;++_[k].sz;
	if(~i)update(_[k].son[(x>>i)&1],x,i-1);
}
void inquiry(int k,int x,int i){if(~i){
	_b=(x>>i)&1;
	if(_[_[k].son[_b]].sz)inquiry(_[k].son[_b],x,i-1);
	else _v+=1<<i,inquiry(_[k].son[!_b],x,i-1);
}}
inline void _init(){
	static int i;
	for(i=1;i<=_tot;++i)_[i].son[0]=_[i].son[1]=_[i].sz=0;
	_rt=_tot=0;
}
struct node{
	int v,id;node()=default;
	node(int _v,int _id):v(_v),id(_id){}
}p[N],pl[N],pr[N];
inline int build_(int l,int r,int j){
	if(l^r){
		int mid=(l+r)>>1,tmp=++nn;
		son[tmp][0][j]=build_(l,mid,j);
		son[tmp][1][j]=build_(mid+1,r,j);
		return tmp;
	}
	return p[l].id;
}//权值相同时建树 
int build(int l,int r,int d,int j){
	int i;
	if(l^r&&~d){
		int lcnt=0,rcnt=0,tmp;bool b;
		for(i=l;i<=r;++i){
			b=(p[i].v>>d)&1;
			if(b)pr[++rcnt]=p[i];
			else pl[++lcnt]=p[i];
		}
		for(i=1;i<=lcnt;++i)p[l+i-1]=pl[i];
		for(i=1;i<=rcnt;++i)p[r-i+1]=pr[i];
		if(lcnt&&rcnt){
			tmp=++nn;w[tmp][j]=inf;
			son[tmp][0][j]=build(l,l+lcnt-1,d-1,j);
			for(i=r-rcnt+1;i<=r;++i){
				_v=0,inquiry(_rt,p[i].v,K);
				w[tmp][j]=min(w[tmp][j],_v);
			}
			son[tmp][1][j]=build(r-rcnt+1,r,d-1,j);
			return tmp;
		}
		else return build(l,r,d-1,j);
	}
	else {update(_rt,p[l].v,K);return build_(l,r,j);}
}//建kruskal重构树 
int dfn[N][3],dfnr[N][3],rev[N],sz[N][3],f[N][19][3];
void dfs(int x,int anc,int j){
	f[x][0][j]=anc;int i,y;
	for(i=1;i^19;++i)f[x][i][j]=f[f[x][i-1][j]][i-1][j];
	if(y=son[x][0][j])dfs(y,x,j),sz[x][j]+=sz[y][j];
	if(y=son[x][0][j])dfn[x][j]=dfn[y][j];
	if(y=son[x][1][j])dfs(y,x,j),sz[x][j]+=sz[y][j];
	else dfn[x][j]=++tt,sz[x][j]=1;
}
void init(){
	register int i,j,rt;
	for(j=0;j<3;++j){
		for(i=1;i<=n;++i)p[i]=node(a[i][j],i);
		nn=n;rt=build(1,n,K,j);tt=0;dfs(rt,0,j);w[0][j]=inf;
		for(i=1;i<=nn;++i)dfnr[i][j]=dfn[i][j]+sz[i][j]-1;
		_init();
	}
	for(i=1;i<=n;++i)if(sz[i][0]==1)rev[dfn[i][0]]=i;
}
inline int find(int x,int v,int j){
	static int i;
	for(i=18;~i;--i)if(w[f[x][i][j]][j]<=v)x=f[x][i][j];
	return x;
}//倍增 
struct cdq{
	int a,b,c,id;char opt;cdq()=default;//opt=0 : mdf || opt=1,-1 : inq
	cdq(int _a,int _b,int _c,int _id,char _opt):
		a(_a),b(_b),c(_c),id(_id),opt(_opt){}
}q[N<<2],q0[N<<2];
inline bool cmpa(cdq x,cdq y){return x.a^y.a?x.a<y.a:!x.opt;}
inline bool cmpb(cdq x,cdq y){return x.b^y.b?x.b<y.b:!x.opt;}
int t_[N],ti,res,t[3],ans[N];
#define lowbit(i) i&(-i)
inline void update(int pos,int v){for(ti=pos;ti<=n;ti+=lowbit(ti))t_[ti]+=v;}
inline void inquiry(int pos){res=0;for(ti=pos;ti;ti-=lowbit(ti))res+=t_[ti];}
void solve(int l,int r){if(l^r){
	int mid=(l+r)>>1,i;
	solve(l,mid);solve(mid+1,r);
	merge(q+l,q+mid+1,q+mid+1,q+r+1,q0+l,cmpb);
	for(i=l;i<=r;++i)q[i]=q0[i];
	for(i=l;i<=r;++i){
		if(q[i].opt&&q[i].a>mid)inquiry(q[i].c),ans[q[i].id]+=res*q[i].opt;
		else if(!q[i].opt&&q[i].a<=mid)update(q[i].c,1);
	}
	for(i=l;i<=r;++i)if(!q[i].opt&&q[i].a<=mid)update(q[i].c,-1);
}}//cdq
inline void cdq_add(int i){
	static int la,ra,lb,rb,lc,rc;
	la=dfn[t[0]][0]-1,ra=dfnr[t[0]][0];
	lb=dfn[t[1]][1]-1,rb=dfnr[t[1]][1];
	lc=dfn[t[2]][2]-1,rc=dfnr[t[2]][2];
	q[++tot]=cdq(ra,rb,rc,i,1);q[++tot]=cdq(la,lb,lc,i,-1);
	q[++tot]=cdq(la,rb,rc,i,-1);q[++tot]=cdq(ra,lb,lc,i,1);
	q[++tot]=cdq(ra,lb,rc,i,-1);q[++tot]=cdq(la,rb,lc,i,1);
	q[++tot]=cdq(ra,rb,lc,i,-1);q[++tot]=cdq(la,lb,rc,i,1);
}//三维差分 
main(){
	read(n);read(m);register int i,j;
	for(j=0;j<3;++j)for(i=1;i<=n;++i)read(a[i][j]);
	init();
	for(i=1;i<=m;++i){
		for(j=0;j<3;++j)read(v),read(x),t[j]=find(x,v,j);
		cdq_add(i);
	}
	for(i=1;x=rev[i],i<=n;++i)q[++tot]=cdq(i,dfn[x][1],dfn[x][2],0,0);
	sort(q+1,q+tot+1,cmpa);
	for(i=1;i<=tot;++i)q[i].a=i;
	solve(1,tot);
	for(i=1;i<=m;++i)write(ans[i]),putchar('\n');
}