「JOISC 2020 Day2」变色龙之恋（交互题）（分治）（并查集）

本文主要是介绍「JOISC 2020 Day2」变色龙之恋（交互题）（分治）（并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

$O(n^2)$ 做法：两两查询一次，那么给颜色数为 1 的数对连边，那么一个点可以连出 1 或 3 条边
对于一条的可以直接确定，对于 3 条的，假设当前位 $i$ ，它喜欢的为 $x$ ，喜欢它的为 $y$ ，颜色相同的为 $z$ ，那么当且仅当查询 $(i, y, z)$ 时为 1，如果我们给 $(i, y), (i, z)$ 打上标记，那么两个颜色相同当且仅当这条边被两次打上标记
利用二分图的性质，对于已知的边，可以把 $[1, i)$ 的点分成两个集合，集合内均无边，然后在集合中分治，查询次数 $3\log n$ ，并且这个可以用并查集维护
复杂度 $O(n^2\log n)$ ，查询次数 $O(n(3\log n+6))$

#include "chameleon.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
cs int N = 1050;
int fa[N], c[N], id[N], d[N];
vector<int> G[N];
int fnd(int x){ return x==fa[x]?x:fnd(fa[x]); }
int fndc(int x){ return x==fa[x]?0:c[x]^fndc(fa[x]); }
void mrg(int u, int v){int fx=fnd(u), fy=fnd(v);if(d[fx]>d[fy]) swap(fx,fy), swap(v,u); if(fx==fy) return;fa[fx]=fy; d[fy]=max(d[fy],d[fx]+1);c[fx]=fndc(u)^fndc(v)^1;
}
bool work_e(vector<int> S, int l, int r, int u, bool flg=0){if(G[u].size()==3) return false; if(l>r) return false;if(!flg){vector<int> T; T.pb(u);for(int i=l; i<=r; i++) T.pb(S[i]);int c = Query(T); if(c>r-l+1) return false;	}if(l==r){ G[u].pb(S[l]);G[S[l]].pb(u);mrg(u,S[l]); return true;}int mid = (l+r) >> 1;bool t = work_e(S,l,mid,u,false);work_e(S,mid+1,r,u,!t); return true;
}
void Solve(int n){srand(time(0));for(int i=1; i<=n+n; i++) id[i]=i;random_shuffle(id+1,id+n+n+1);for(int i=1; i<=n+n; i++) fa[i]=i, c[i]=0;for(int i=1; i<=n+n; i++){vector<int> A, B;for(int j=1; j<i; j++) if(G[id[j]].size()!=3)fndc(id[j])?B.pb(id[j]):A.pb(id[j]);work_e(A,0,A.size()-1,id[i]);work_e(B,0,B.size()-1,id[i]);}static int mp[N][N], vis[N][N];for(int i=1; i<=n+n; i++) if(G[i].size()==1&&!vis[i][G[i][0]]) vis[i][G[i][0]]=vis[G[i][0]][i]=1, Answer(i,G[i][0]);for(int i=1; i<=n+n; i++) if(G[i].size()>1){assert(G[i].size()==3);for(int u=0; u<3; u++) if(G[G[i][u]].size()==3)for(int v=u+1; v<3; v++) if(G[G[i][v]].size()==3){vector<int> S; S.pb(i), S.pb(G[i][u]), S.pb(G[i][v]);if(Query(S)==1){++mp[i][G[i][u]], ++mp[i][G[i][v]];++mp[G[i][u]][i], ++mp[G[i][v]][i];break;}}}for(int i=1; i<=n+n; i++)for(int j=i+1; j<=n+n; j++)if(mp[i][j]==2) Answer(i,j);
}