Aly_

题意简述

​ $N$ 点 $M$ 边无向图，形态未知。每个点有状态：关 / 开。现需通过如下四种操作确定图的形态：

• 选定一个点，反转它及其邻点状态；
• 查询一个点状态；
• 记录一条无向边；
• 询问与一个点相连的无向边是否都被记录。

​ 其中，第一、三、四种操作次数分别不多于 $L_m,L_q,L_c$。

分析 & 解法

​ 顺着部分分推即可。以下展现思路过程。

1. 首先看到暴力 20 分：对每个点修改再询问所有点即可。

void cal0(){
	for(int i=1;i<n;i++){
		modify(i-1),fl[i]^=1;
		for(int j=i+1;j<=n;j++){
			if(query(j-1)!=fl[j])fl[j]^=1,report(i-1,j-1);
		}
	}
}

​ 开始做部分分。

1. 考虑 $A$ 部分性质。发现：整张图被分成了 $\frac{n}{2}$ 对点，只有同一对点之间有连边。
2. 问题转化成求与每一个点配对的点。观察数据范围，发现需要一个 $O(n\log n)$ 左右的做法。猜测会出现大概是二分 / 分治的做法。
3. 不妨尝试：把所有点分成两半，只修改其中一半的点再查询。
4. 如果查询到一个点状态改变了，说明其配对点一定在进行了修改操作的点集中。于是可以继续分治下去做。

​ 不难想到运用二进制的思想。总共进行 $\log n$ 轮操作，第 $i$ 次操作修改所有二进制第 $i-1$ 位为 $1$ 的点并查询所有点，即可得到所有点的配对点的当前位是否为 $1$。全部进行完后，所有点的配对点的所有位都确定了。

void cal1(){
	for(int i=2;i<=n;i++)logn[i]=logn[i/2]+1;
	for(int i=0;i<=logn[n];i++){
		for(int j=0;j<n;j++)if(j&(1<<i))modify(j),fl[j]^=1;
		for(int j=0;j<n;j++)if(query(j)!=fl[j])fl[j]^=1,pa[j]|=(1<<i);
	}
	for(int i=0;i<n;i++)if(i<pa[i])report(i,pa[i]);
}

​ $B$ 的做法相对简单且包含在 $D$ 中，先考虑 $C$。

1. 观察解决 $A$ 部分的方法，其具有很强的可扩展性。
2. 事实上可以把该方法重述如下：选取点集 $S,T$，进行 $\log n$ 轮操作，第 $i$ 次操作修改 $T$ 中所有二进制第 $i-1$ 位为 $1$ 的点并查询所有 $S$ 中的点，如果当前点的状态改变则在当前位记 $1$。
3. 考虑什么时候当前点的状态会改变：$T$ 中有奇数个当前位为 $1$ 的点与当前点相邻。也就是说，$T$ 中所有与之相邻的点，其标号异或和在当前位为 $1$。
4. 于是，该操作得到的是对于每一个 $S$ 中的点 $x$，$T$ 中所有与它相邻的点标号异或和，记为 $pa_x$。
5. 考虑链的情况。取 $S,T$ 为全集，做一遍操作，得到所有点的 $pa$。

​ 注意到链的端点（设为 $a$）只有一个点（设为 $b$）与之相连，所以 $pa_x=b$，因而确定了一条边。而且，与 $b$ 相邻的只有两个点，其中一个就是 $a$，因此，可以在 $b$ 的答案中异或 $a$ 以计算与 $b$ 相邻的另一个点，继续递推。

​ 而链的端点是易求的：把所有点修改一遍，状态改变的点就是链的端点。

​ 下面考虑 $D$。

1. 注意到，如果确定所有叶子，则可以像链一样从下往上 “ 剥叶子 ”，得到所有点的父亲。
2. 然后有一个看起来笨蛋却常常被忽略的事实：如果修改点 $x$ 后点 $y$ 的状态改变，则 $x$ 和 $y$ 有边。

​ 如果发现该事实解法就显而易见了：对于每个点 $x$，修改它，看 $pa_x$ 状态变不变。如果变了，记录那条边，然后询问 $x$ 相连的边是否找尽，如果是，$x$ 就是叶子了。当然最后还要把 $x$ 修改回来防止不必要的影响。

void cal3(){
	for(int i=2;i<=n;i++)logn[i]=logn[i/2]+1;
	for(int i=0;i<=logn[n];i++){
		for(int j=0;j<n;j++)if(j&(1<<i))modify(j),fl[j]^=1;
		for(int j=0;j<n;j++)if(query(j)!=fl[j])fl[j]^=1,pa[j]|=(1<<i);
	}
	for(int j=0;j<n;j++){
		modify(j),fl[j]^=1;
		if(pa[j]<n&&query(pa[j])!=fl[pa[j]]){
if(se.find(make_pair(pa[j],j))==se.end()&&se.find(make_pair(j,pa[j]))==se.end())report(j,pa[j]),se.insert(make_pair(j,pa[j]));
			if(check(j))qu.push(pa[j]),inq[j]=1,pa[pa[j]]^=j;
		}
		modify(j),fl[j]^=1;
	}
	while(!qu.empty()){
		int nt=qu.front();
		qu.pop();
		if(inq[nt])continue;
		if(inq[nt]!=1){
			modify(nt),fl[nt]^=1;
			if(pa[nt]<n&&query(pa[nt])!=fl[pa[nt]]){
if(se.find(make_pair(pa[nt],nt))==se.end()&&se.find(make_pair(nt,pa[nt]))==se.end())report(nt,pa[nt]),se.insert(make_pair(nt,pa[nt]));
				if(check(nt)){
					pa[pa[nt]]^=nt;
					qu.push(pa[nt]);
					inq[nt]=1;
				}
				
			}
			modify(nt),fl[nt]^=1;
		}
	}
}

​ 下面考虑正解。

1. 通过观察题目标签猜测本题需要某些随机化的手段。（但随机化的标签现在没了？）
2. 一个比较好想的思路是多次随机 $S,T$ 点集，找出它们间的所有边。
3. 可以随机 $T$ 点集，再找到一些点，使之与 $T$ 中的点只有一个相邻。因为图密度不大，这样的效率看起来很高。

​ 可以做个试验。随机一个大小为 $B$ 的点集 $T$，对于其余所有点，找到所有与奇数个 $T$ 中的点相邻的点，把其作为 $S$ 的候选，统计其中有多少只与一个 $T$ 中的点相邻。

​ 取 $n=100000,m=200000$ 随机图，发现当 $B=1000$ 时，$|S|$ 会达到 $4000\sim 6000$ 左右，其中大约有 $2000$ 个点是有效（只与一个 $T$ 中点相邻）的。

​ 计算一下操作代价发现不计常数的情况下是可过的。

​ 于是有了一个很笨蛋的做法：随机一个大小为 $B=\frac{n}{100}$ 的点集 $T$，对于其余所有点，找到所有与奇数个 $T$ 中的点相邻的点，把其加入 $S$。进行一次操作，求出所有 $pa$。对于每个 $S$ 中的点，验证其 $pa$ 是否确实和它有边相连。做完后，检查所有 $T$ 和 $S$ 中的点，如果与其相连的边全连完了，就在图中去掉它。不断去除直至剩余点集为空（或足够小）。

​ 在 $n=100000$ 的图上实现之，发现询问次数达到 $2*10^7$。考虑到这个做法看上去就很笨蛋，可以考虑卡常。

​ 一个优化是记录所有与当前点相连的边，找 $S$ 的时候把这些边纳入考虑：考察这些边另一边点与当前 $T$ 的交集，求奇偶性的时候异或上交集大小。实测可以减小常数 $\frac{2}{3}$ 左右。

​ 再调调 $B$ 就过了。

void calc(){
	for(int i=2;i<=n;i++)logn[i]=logn[i/2]+1;
	B=max(1,n/100);
	int tn=n,ncol=1;
	while(tn){
		if(tn>=100000)B=max(1,tn/10);
		else B=max(1,(int)(sqrt(tn)*log(tn)));
		if(n%10==4)B=max(1,(int)(sqrt(n)));
		B=min(B,tn);
		pt=0;ncol++;
		for(int i=0;i<n;i++)if(!afl[i])t[++pt]=i;
		for(int i=2;i<=pt;i++)swap(t[i],t[rd()%i+1]);
		for(int i=1;i<=B;i++)ft[t[i]]=i,modify(t[i]),fl[t[i]]^=1,tfl[t[i]]=ncol;
		p0=0;
		for(int i=0;i<n;i++){
			if(afl[i])continue;
			tg[i]=0;int lg=0;
			for(int j=0;j<ve[i].size();j++){
				if(tfl[ve[i][j]]==ncol)tg[i]^=1,lg^=(ft[ve[i][j]]-1);
			}
			if((query(i)!=fl[i])^tg[i]){
				fl[i]^=1,q0[++p0]=i,pa[p0]=lg;
			}
		}
		for(int i=0;i<=logn[B];i++){
			for(int j=1;j<=B;j++)if((j-1)&(1<<i))modify(t[j]),fl[t[j]]^=1;
			for(int j=1;j<=p0;j++)if(query(q0[j])!=fl[q0[j]])fl[q0[j]]^=1,pa[j]^=(1<<i);
		}
		for(int i=1;i<=B;i++)if(query(t[i])!=fl[t[i]])fl[t[i]]^=1;
		for(int i=1;i<=p0;i++){
			if(pa[i]>=B)continue;
			modify(q0[i]),fl[q0[i]]^=1;
			int nt=t[pa[i]+1];
			if(tfl[nt]){
				long long nh=hsh(q0[i],nt);
				if((nse.find(nh)==nse.end())&&query(nt)!=fl[nt]){
					report(q0[i],nt);
					ve[q0[i]].push_back(nt),ve[nt].push_back(q0[i]);
					nse.insert(nh);
				}
			}
			modify(q0[i]),fl[q0[i]]^=1;
		}
		for(int i=1;i<=B;i++){
			if(check(t[i]))afl[t[i]]=1,tn--;
		}
		for(int i=1;i<=p0;i++){
			if(tfl[q0[i]]!=ncol&&check(q0[i]))afl[q0[i]]=1,tn--;
		}
	}
}

​