E2 - Bitwise Queries (Hard Version)

题意：

给你长度为n的隐藏的数组，你有三种询问：选两个不同的下标i，j，询问（1）a[i]|a[j]  (2) a[i]&a[j] (3) a[i]^a[j]  

你可以询问至多n+2次（hard verson 为n+1次）

题解：

做n-1次操作——每次询问a[1]^a[i] (i=2,3,4.....n)，记为b[i];

然后有三种情况

1）存在b[i](i=2,3...）为0，说明a[i]==a[1]，这时直接询问a[i]&a[1]即可

2）存在i，j，使得b[i]==b[j]，说明a[i]==a[j]，直接询问a[i]&a[j]即可

3）不是以上两种情况，说明0~n-1都出现了一遍，结合n是二的幂次，异或后的值也是在0~n-1内的

这时找b[i]&b[j]==0的i，j，询问a[i]&a[1](记为x）, 和a[j]&a[1]（记为y），则a[1]=x|y

更简单的，可以找到b[i]=1,b[j]=2（此时满足b[i]&b[j]==0)，然后做上面的操作

 

case 3 正确性证明：

a[i]&a[1]能找出两者同为1的位，不同为1的位体现在b[i]（即a[i]^a[1])中，这样我们就确定了a[1]中除b[i]外的所有位

a[j]&a[1]，我们能确定a[1]中除了b[j]外的所有位

那么如果b[i]&b[j]==0，我们就确定了a[1]的所有位了。

#include<bits/stdc++.h>
using namespace std;

int a[1000005];
map<int,int>mp;

int main()
{
	int n,x;
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		printf("XOR 1 %d\n",i);
		fflush(stdout);
		scanf("%d",&a[i]);
	}
	//case 1
	for(int i=2;i<=n;i++){
		if(a[i]==0){
			printf("OR 1 %d\n",i);
			fflush(stdout);
			scanf("%d",&x);
			printf("! %d ",x);
			for(int j=2;j<=n;j++){
				printf("%d ",a[j]^x);
			}
			printf("\n");
			fflush(stdout);
			return 0;
		}
	}
	//case 2
	int j;
	for(int i=2;i<=n;i++){
		j=mp[a[i]];
		if(j){
			printf("OR %d %d\n",j,i);
			fflush(stdout);
			scanf("%d",&x);
			x^=a[i];
			printf("! %d ",x);
			for(int k=2;k<=n;k++)printf("%d ",a[k]^x);
			printf("\n");
			fflush(stdout);
			mp.clear();
			return 0;
		}
		mp[a[i]]=i;
	}
	//case 3
	int id1,id2,y;
	for(int i=2;i<=n;i++){
		if(a[i]==1){
			id1=i;
		}
		else if(a[i]==2){
			id2=i;
		}
	}
	printf("AND 1 %d\n",id1);
	fflush(stdout);
	scanf("%d",&x);
	printf("AND 1 %d\n",id2);
	fflush(stdout);
	scanf("%d",&y);
	x|=y;
	printf("! %d ",x);
	for(int i=2;i<=n;i++)printf("%d ",a[i]^x);
	printf("\n");
	fflush(stdout);
	return 0;
}