奇奇怪怪的交互题。
有 \(2N\) 只变色龙，每条变色龙有一个性别，一个颜色，和一个喜欢的颜色不同的异性。其中恰好 \(N\) 男 \(N\) 女，\(N\) 种颜色每种颜色恰好两条变色龙。
每次可以选一些变色龙出来，如果第 \(i\) 条龙和它喜欢的龙同时被选了，那么它就变成喜欢龙的颜色，否则不变，返回变色后的颜色数。
\(N\le 500\) ，需要在 \(20000\) 次询问内求出颜色相同的每一对龙。
对于子任务 \(1\) ，所有变色龙都是双向喜欢。那么查询所有二元组 \((i,j)\) ，如果返回 \(1\) 则 \(i,j\) 颜色相同，否则颜色不同。因为如果互相或互相不喜欢，颜色总数都不变。
对于子任务 \(2,3\) ，延续子任务 \(1\) 的思路，查询所有二元组，如果返回 \(1\) ，手玩一下发现有三种情况。第一种是两者颜色相同，第二种是 \(i\) 单向喜欢 \(j\) ，或者是 \(j\) 单向喜欢 \(i\) 。我们在 \(i,j\) 之间连边，一个点的入度为 \(1\) 或 \(3\) 。
入度为 \(1\) ，则与之连边的点和它颜色相同。
入度为 \(3\)，我们找到与之相连的三个点中的两个点，查询当前点和这两个点的集合，如果返回 \(1\) ，则当前点一定单向喜欢第三个点。
这样我们可以在 \(\mathcal{O}(N^2)\) 次询问内找出答案。
对于子任务 \(4\) ，我们发现瓶颈在于连边的过程，而这个子任务中已知性别。
显然连边后的图一定是二分图，因为无论是喜欢关系还是相等关系都是异性之间。
那么对于 \(X\) 中的点，可以快速在 \(Y\) 中二分出连边的三个点，同理对于 \(Y\) 中的点，可以快速在 \(X\) 中二分出连边的三个点。这样询问次数是 \(\mathcal{O}(N\log N)\)。
对于子任务 \(4\)，依次考虑每个点 \(i\) 。首先我们建出前 \(i-1\) 个点的图，这一定是二分图，那么第 \(i\) 个点在二分图的 \(X\) 部和 \(Y\) 部通过二分快速连边。
随着点的加入二分图的 \(X\) 部和 \(Y\) 部会变化，所以每次都要重新 DFS 染色。时间复杂度 \(\mathcal{O}(N^2\log N)\) ，询问次数 \(\mathcal{O}(N\log N)\) 。
#include<bits/stdc++.h>
#include "chameleon.h"
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 1005
using namespace std;
int v[N],ot[N],in[N];vector<int>c[2],a[N];
int ask(vector<int>p,int w,int l,int r){
vector<int>cur;cur.push_back(w);
rep(i,l,r)cur.push_back(p[i-1]);
return Query(cur);
}
void dfs(int x,int op){
v[x]=1;c[op].push_back(x);
for(int i=0;i<(int)a[x].size();i++)
if(!v[a[x][i]])dfs(a[x][i],1-op);
}
void calc(vector<int>u,int x){
if(!u.size())return;
int st=1,sz=u.size();
rep(op,0,2){
if(st>sz||ask(u,x,st,sz)==sz-st+2)return;
int l=st,r=sz,ed=0;
while(l<=r){
int mid=(l+r)>>1;
if(ask(u,x,st,mid)<=mid-st+1)ed=mid,r=mid-1;
else l=mid+1;
}
a[x].push_back(u[ed-1]);a[u[ed-1]].push_back(x);st=ed+1;
}
}
int qry(int x,int y,int z){
vector<int>u;
u.push_back(x);u.push_back(y);u.push_back(z);
return Query(u);
}
void solve(int x){
if(a[x].size()>2){
int i=a[x][0],j=a[x][1],k=a[x][2];
if(qry(x,i,j)==1)ot[x]=k,in[k]=x;
else if(qry(x,j,k)==1)ot[x]=i,in[i]=x;
else ot[x]=j,in[j]=x;
}
}
void Solve(int n){
rep(i,2,n*2){
memset(v,0,sizeof(v));
c[0].clear();c[1].clear();
rep(j,1,i-1)if(!v[j])dfs(j,0);
calc(c[0],i);calc(c[1],i);
}
memset(v,0,sizeof(v));
rep(i,1,n*2)solve(i);
rep(i,1,n*2)if(!v[i]){
if(in[i]){
int cur=0;
for(int j=0;j<=2;j++)if(a[i][j]!=in[i]&&a[i][j]!=ot[i])cur=a[i][j];
Answer(i,cur);v[i]=v[cur]=1;
}
else Answer(i,a[i][0]),v[i]=v[a[i][0]]=1;
}
}