NOIP2023模拟19联测40
异或连通
类似于线段树分治，但是可以在 \(trie\) 树上做。首先根据询问建一棵 \(trie\) 树，然后现在考虑将边插到树上。设插入的边权为 \(c_i\)，因为 \(c_i^x<K\)，所以我们压着上界走，考虑每一位 \(i\)，如果 \(K\) 在第 \(i\) 位上位 \(1\)，那么假如 \(c_i\) 在这位上位 \(1\)，那么在 \(1\) 的儿子上可以压入这条边，而且这个点下面的值异或起来都不会大于 \(K\)。然后再用一个可撤销并查集就可以了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,q,k;
struct asd{
int x,y,c;
}a[N];
int Q[N];
int tr[N*100][2],idx=0;
unordered_map<int,int> rk;
void insert(int x,int p){
int u=0;
for(int i=32;i>=0;i--){
int ch=((x>>i)&1);
if(!tr[u][ch]) tr[u][ch]=++idx;
u=tr[u][ch];
}
rk[p]=u;
}
vector<int> s[N*100];
void updata(int x){
int w=a[x].c;
int u=0;
for(int i=32;i>=0;i--){
int p=((k>>i)&1);
int ch=(((k^w)>>i)&1);
if(p==1 && tr[u][(w>>i)&1]) s[tr[u][(w>>i)&1]].push_back(x);
u=tr[u][ch];
if(!u) break;
}
}
struct qwe{
int x,fx,siz;
}b[N*10];
int top=0;
int fa[N],siz[N];
int get_fa(int x){
if(fa[x]==x) return x;
else return get_fa(fa[x]);
}
int ans=0;
unordered_map<int,int> anss;
void dfs(int x){
int lim=top;
for(int p=0;p<s[x].size();p++){
int i=s[x][p];
int fx=get_fa(a[i].x),fy=get_fa(a[i].y);
if(fx==fy) continue;
if(siz[fx]>siz[fy]){
b[++top]={fy,fx,siz[fx]};
ans=ans-(siz[fx]-1)*siz[fx]/2;
ans=ans-(siz[fy]-1)*siz[fy]/2;
fa[fy]=fx;
siz[fx]+=siz[fy];
ans=ans+(siz[fx]-1)*siz[fx]/2;
}
else{
b[++top]={fx,fy,siz[fy]};
ans=ans-(siz[fx]-1)*siz[fx]/2;
ans=ans-(siz[fy]-1)*siz[fy]/2;
fa[fx]=fy;
siz[fy]+=siz[fx];
ans=ans+(siz[fy]-1)*siz[fy]/2;
}
}
anss[x]=ans;
if(tr[x][0]) dfs(tr[x][0]);
if(tr[x][1]) dfs(tr[x][1]);
while(top>lim){
fa[b[top].x]=b[top].x;
ans-=(siz[b[top].fx]-1)*siz[b[top].fx]/2;
siz[b[top].fx]=b[top].siz;
ans+=(siz[b[top].fx]-1)*siz[b[top].fx]/2+(siz[b[top].x]-1)*siz[b[top].x]/2;
top--;
}
}
signed main(){
// freopen("data.in","r",stdin);
// freopen("cnt.out","w",stdout);
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
scanf("%lld%lld%lld%lld",&n,&m,&q,&k);
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].c);
for(int i=1;i<=q;i++){
scanf("%lld",&Q[i]);
insert(Q[i],i);
}
for(int i=1;i<=m;i++){
if(a[i].x==a[i].y) continue;
updata(i);
}
for(int i=1;i<=n;i++){
fa[i]=i,siz[i]=1;
}
dfs(1);
for(int i=1;i<=q;i++){
printf("%lld\n",anss[rk[i]]);
}
}