【纪中集训2019.3.14】小凯的疑惑

题目

描述:

(n)个点的完全图，每个点有一个(C)为二进制权值(X_{i})，$W(u,v) = X_{u} xor X_{v} $

求这个图的最小生成树，支持(Q)次修改，每次修改将所有点权值(+V)，询问具有后效性；

题目：

(1 le n le 20000 , C le 14 , 1 le Q le 20000)

题解：

算法一：
首先答案和(n)无关权值只有(2^C)中，询问最多也是(2^C)种，可以预处理所有询问；
考虑经典的异或生成树的做法；
按照二进制的最高位分治，内部的边比跨越两边的边都要优，在(Trie)里查找两两连边的最小值；
复杂度：(O(2^C imes C^22^C)) ；
算法二：
对于一个询问(Q_{i})，将它分成后(B)位和前(C - B) 位；
在分治树上，记从下到上为(0 o C-1) 层 ;
$Q_{i} (后)C-B(位的贡献相当于将第)B$层的分治子树向右整体平移；
(Q_{i})前(B)位的贡献相当于只在(B)层之前的叶子平移，对B层以上的结构没有影响；
预处理一个询问的前(B)位确定时(B) 层的每个节点分治下去的答案和两两之间合并的答案；
对于后$C - B $位直接分治；
复杂度：(O( 2^{C+B}B^2 + 2^{2C-B}B))
大致(B)取(frac{n}{2})比较好
算法三：
对前(B)层的求解可以再进行优化：
预处理前(A(A lt B))每个叶子节点的答案和两两之间合并的答案；
考虑到(A)比较小，可以直接枚举(2^{2^{A}})颗子树暴力求解，当分治到第(A)层时直接调用答案；
复杂度：(O((2^{2^{A}+1})2^AA + 2^{2^{A}}2^AA^{2} + 2^{C}2^{B-A}(B-A)^2 + 2^{2C-A}(B-A) + 2^{2C-B}(C-B)^2))
（省略一些近似于常数的东西可能大家的写法有点出入）

这样子(C==14)的情况(A)取(3)，(B)取(7)即可；、

#include<bits/stdc++.h>
#define fir first
#define sec second 
#define mk make_pair
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int,int>pii;
int n,q,A,B,C,sum[1<<15],a[1<<15],mask[1<<15];
int v[1<<3],g[1<<8],G[1<<8][1<<8],f[1<<7][1<<7],F[1<<7][1<<7][1<<7],ans[1<<15];
inline int min(int x,int y){return x<y?x:y;}
struct Trie{
	int sz,ch[1<<15][2],val[1<<15];
	void init(){
		for(int i=1;i<=sz;++i)ch[i][0]=ch[i][1]=val[i]=0;
		sz=1;
	}
	void ins(int x,int l,int r,int y){
		int now=1;
		for(int i=r-1;i>=l;--i){
			int t=x>>i&1;
			if(ch[now][t])now=ch[now][t];
			else ch[now][t]=++sz,now=sz;
		}
		val[now]=y;
	}
	pii que(int x,int l,int r){
		int res=0,now=1;
		for(int i=r-1;i>=l;--i){
			int t=x>>i&1;
			if(ch[now][t])now=ch[now][t];
			else now=ch[now][t^1],res^=1<<i;
		}
		return mk(res,val[now]);
	}
}T;
bool ask(int x,int y){
	if(!x)return sum[y-1];
	return sum[y-1]-sum[x-1];
}
void init(){
	for(int i=0;i<1<<C;++i)a[i+(1<<C)]=a[i];
	for(int i=0;i<1<<C+1;++i)sum[i]=sum[i-1]+a[i];
	for(int i=0;i<1<<C;++i)
	for(int j=0;j<1<<A;++j)mask[i]|=a[i+j]<<j;
	for(int i=0;i<1<<C;++i)mask[i+(1<<C)]=mask[i];
}
int solveg(int l,int r){
	if(l+1==r)return 0;
	int mid=(l+r)>>1,fg;
	fg=0;
	for(int i=l;i<mid;++i)if(v[i]){fg=1;break;}
	if(!fg)return solveg(mid,r);
	fg=0;
	for(int i=mid;i<r;++i)if(v[i]){fg=1;break;}
	if(!fg)return solveg(l,mid);
	T.init();
	for(int i=l;i<mid;++i)if(v[i])T.ins(i,0,A,i);
	int re=inf;
	for(int i=mid;i<r;++i)if(v[i])re=min(re,T.que(i,0,A).fir);
	return re + solveg(l,mid) + solveg(mid,r);
}
int solvef(const int s,int l,int r){
	if(l+1==r)return g[mask[s+(l<<A)]];
	int mid=(l+r)>>1,fg;
	fg=0;
	for(int i=l;i<mid;++i)if(ask(s+(i<<A),s+(i+1<<A))){fg=1;break;}
	if(!fg)return solvef(s,mid,r);
	fg=0;
	for(int i=mid;i<r;++i)if(ask(s+(i<<A),s+(i+1<<A))){fg=1;break;}
	if(!fg)return solvef(s,l,mid);
	T.init();
	for(int i=l;i<mid;++i)if(ask(s+(i<<A),s+(i+1<<A))){
		T.ins(i<<A,A,B,s+(i<<A));
	}
	int re=inf;
	for(int i=mid;i<r;++i)if(ask(s+(i<<A),s+(i+1<<A))){
		pii r = T.que(i<<A,A,B);
		re = min(re, r.fir + G[mask[s+(i<<A)]][mask[r.sec]]);
	}
	return re + solvef(s,l,mid) + solvef(s,mid,r); 
}
int solveans(const int s,int l,int r){
	int S1=(1<<B)-1,S2=(1<<C-B)-1;
	if(l+1==r)return f[s&S1][l+(s>>B)&S2];
	int mid=(l+r)>>1,fg;
	fg=0;
	for(int i=l;i<mid;++i)if(ask(s+(i<<B),s+(i+1<<B))){fg=1;break;}
	if(!fg)return solveans(s,mid,r);
	fg=0;
	for(int i=mid;i<r;++i)if(ask(s+(i<<B),s+(i+1<<B))){fg=1;break;}
	if(!fg)return solveans(s,l,mid);
	T.init();
	for(int i=l;i<mid;++i)if(ask(s+(i<<B),s+(i+1<<B))){
		T.ins(i<<B,B,C,i+(s>>B)&S2);
	}
	int re=inf;
	for(int i=mid;i<r;++i)if(ask(s+(i<<B),s+(i+1<<B))){
		pii r = T.que(i<<B,B,C);
		re = min(re, r.fir + F[s&S1][i+(s>>B)&S2][r.sec]);
	}
	return re + solveans(s,l,mid) + solveans(s,mid,r);
}
void calcg(){
	for(int i=0;i<1<<(1<<A);++i){
		for(int j=0;j<1<<A;++j)v[j]=i>>j&1;
		g[i]=solveg(0,1<<A);
	}
}
void calcG(){
	for(int i=0;i<1<<(1<<A);++i){
		T.init();
		for(int j=0;j<1<<A;++j)if(i>>j&1){T.ins(j,0,A,j);}
		for(int j=0;j<1<<A;++j){G[i][1<<j]=T.que(j,0,A).fir;}
		for(int j=0;j<1<<(1<<A);++j){if(j^(j&-j))G[i][j]=min(G[i][j^(j&-j)],G[i][j&-j]);}
	}
}
void calcf(){
	for(int i=0;i<1<<B;++i)
	for(int j=0;j<1<<C-B;++j){
		f[i][j]=solvef(i,j<<B-A,j+1<<B-A);
	}
}
void calcF(){
	for(int i=0;i<1<<B;++i)
	for(int j=0;j<1<<C-B;++j){
		T.init();
		int fg=0;
		for(int k=j<<B-A;k<j+1<<B-A;++k)if(ask(i+(k<<A),i+(k+1<<A))){
			T.ins(k<<A,A,B,i+(k<<A));fg=1;
		}
		if(!fg)continue;
		for(int k=0;k<1<<C-B;++k){
			fg=0;
			for(int l=k<<B-A;l<k+1<<B-A;++l)if(ask(i+(l<<A),i+(l+1<<A))){fg=1;break;}
			if(!fg){F[i][j][k]=0;continue;}
			F[i][j][k]=inf;
			for(int l=k<<B-A;l<k+1<<B-A;++l)if(ask(i+(l<<A),i+(l+1<<A))){
				pii r=T.que(l<<A,A,B);
				F[i][j][k]=min(F[i][j][k], r.fir+G[mask[i+(l<<A)]][mask[r.sec]]);
			}
		}
	}
}
void calcans(){
	for(int i=0;i<1<<C;++i)
	ans[i]=solveans(i,0,1<<C-B);
}
int main(){
	freopen("xor.in","r",stdin);
	freopen("xor.out","w",stdout);
	scanf("%d%d",&n,&C);
	B=C>>1;A=B>>1;
	for(int i=1,x;i<=n;++i)scanf("%d",&x),a[x]=1;
	init();
	calcg();calcG();
	calcf();calcF();
	calcans();
	scanf("%d",&q);
	int S=(1<<C)-1;
	for(int i=1,x,y=0;i<=q;++i){
		scanf("%d",&x);
		y=(y+S+1-x)&S;
		printf("%d
",ans[y]);	
	}
	return 0;
}

【纪中集训2019.3.14】小凯的疑惑

题目

描述:

题目：

题解：

算法一：

算法二：

算法三：