C++14(g++5.4) 解法, 执行用时: 393ms, 内存消耗: 6248K, 提交时间: 2020-01-10 14:08:46
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
const int N=1e5+10;
int cnt,st[N],n,q;
struct node{
int ch[2],fa,re,val,col;
}t[N];
inline void push_up(int p){
t[p].val=t[ls(p)].val|t[rs(p)].val|(1LL<<t[p].col);
}
inline void push_re(int p){swap(ls(p),rs(p)); t[p].re^=1;}
inline void push_down(int p){
if(!t[p].re) return;
if(ls(p)) push_re(ls(p)); if(rs(p)) push_re(rs(p)); t[p].re^=1;
}
inline bool isroot(int x){return ls(t[x].fa)!=x&&rs(t[x].fa)!=x;}
inline void rotate(int x){
int y=t[x].fa,z=t[y].fa,k=rs(y)==x,w=t[x].ch[!k];
if(!isroot(y)) t[z].ch[rs(z)==y]=x; t[x].ch[!k]=y; t[y].ch[k]=w;
if(w) t[w].fa=y; t[y].fa=x; t[x].fa=z; push_up(y);
}
inline void splay(int x){
cnt=1; st[cnt]=x; int y=x;
while(!isroot(y)) st[++cnt]=y=t[y].fa;
while(cnt) push_down(st[cnt--]);
while(!isroot(x)){
int y=t[x].fa,z=t[y].fa;
if(!isroot(y)) rotate((ls(y)==x)^(ls(z)==y)?x:y); rotate(x);
}push_up(x);
}
inline void access(int x){
for(int y=0;x;x=t[y=x].fa) splay(x),rs(x)=y,push_up(x);
}
inline void makeroot(int x){
access(x); splay(x); push_re(x);
}
inline int find(int x){
access(x); splay(x); while(ls(x)) push_down(x),x=ls(x);
splay(x); return x;
}
inline void split(int x,int y){
makeroot(x); access(y); splay(y);
}
inline void link(int x,int y){
if(find(x)==find(y)) return ;
int tc=t[x].col+t[y].col>>1;
makeroot(x),t[x].fa=y,t[x].col=tc,makeroot(y),t[y].col=tc;
}
inline void cut(int x,int y){
makeroot(x);
if(find(y)==x&&t[y].fa==x&&!ls(y)) t[y].fa=rs(x)=0,push_up(x);
}
inline int ask(int x,int y){
if(find(x)!=find(y)) return -1;
split(x,y); int tc=t[y].val,res=0;
for(;tc;tc-=tc&(-tc)) res++;
return res;
}
signed main(){
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>t[i].col;
for(int i=1,op,x,y;i<=q;i++){
scanf("%lld %lld %lld",&op,&x,&y);
if(op==1) link(x,y);
else printf("%lld\n",ask(x,y));
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 294ms, 内存消耗: 118648K, 提交时间: 2020-03-17 16:35:02
#include<bits/stdc++.h>
using namespace std;
const int MAX=3e5+10;
typedef long long ll;
struct lenka
{
int op,x,y;
}a[MAX];
int p[MAX];
int f(int x)
{
return p[x]==x?p[x]:p[x]=f(p[x]);
}
vector<int>e[MAX];
int w[MAX];
int nex[MAX][21];
int d[MAX];
int num[MAX][61];
void dfs(int k,int fa,int dep)
{
d[k]=dep;
nex[k][0]=fa;
num[k][w[k]]++;
for(int j=1;j<=60;j++)
num[k][j]+=num[fa][j];
for(int i=1;i<=20;i++)
nex[k][i]=nex[nex[k][i-1]][i-1];
for(int i=0;i<e[k].size();i++)
{
int nex=e[k][i];
if(nex==fa) continue;
dfs(nex,k,dep+1);
}
}
int LCA(int x,int y)
{
if(x==y) return x;
if(d[x]>d[y]) swap(x,y);
for(int i=20;i>=0;i--)
{
if(d[x]<d[y]&&d[nex[y][i]]>=d[x]) y=nex[y][i];
}
for(int i=20;i>=0;i--)
{
if(nex[x][i]!=nex[y][i])
{
x=nex[x][i];
y=nex[y][i];
}
}
if(x!=y) return nex[x][0];
return x;
}
int ans[MAX];
int main()
{
memset(ans,0,sizeof ans);
memset(nex,0,sizeof nex);
memset(d,0,sizeof d);
memset(num,0,sizeof num);
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=q;i++)
scanf("%d%d%d",&a[i].op,&a[i].x,&a[i].y);
for(int i=1;i<=n;i++)
p[i]=i;
for(int i=1;i<=q;i++)
{
int fx=f(p[a[i].x]);
int fy=f(p[a[i].y]);
if(a[i].op==1)
{
if(fx==fy) continue;
w[a[i].x]=w[a[i].y]=(w[a[i].y]+w[a[i].x])/2;
e[a[i].x].push_back(a[i].y);
e[a[i].y].push_back(a[i].x);
p[fx]=fy;
}
else
{
if(fx!=fy) ans[i]=-1;
}
}
for(int i=1;i<=n;i++)
if(p[i]==i) dfs(i,0,1);
for(int i=1;i<=q;i++)
{
if(a[i].op==2)
{
if(ans[i]==-1)
{
puts("-1");
continue;
}
int x=a[i].x,y=a[i].y;
int lca=LCA(x,y);
int tot=0;
for(int j=1;j<=60;j++)
{
if(w[lca]==j) tot+=(num[x][j]+num[y][j]+1-2*num[lca][j]>0);
else tot+=(num[x][j]+num[y][j]-2*num[lca][j]>0);
}
printf("%d\n",tot);
}
}
return 0;
}