Cfdiv2 fixed point guessing- (interval answer two points)

D

The question ：
Is to give you a 1 To n Array of , But among them n+1/2 Secondary exchange , Each number will only be exchanged once , So only one number has not been exchanged . Then you can query 15 Time , One interval at a time , Will return to you the number of this interval from small to large after the order . Now I ask you which number has not been exchanged .

reflection ：
At the beginning 15 I know it's two points at a time , But I thought it was dfs Two points , Every recursive judgment . But I feel it's not easy to write . Actually , For dichotomy , You can divide the answer in which range . That is to judge first l To r, If the answer is in here ,r = mid. otherwise l = mid+1. That is, in another interval . This is simply to judge in which range , With theout an answer, better is worse . But how to judge , In fact, for , Number of inputs x, If x stay l To r Inside , That means he changed it for one of them , Then the number in it will appear twice , Otherwise, it would be 0 Time . But which number without exchange will contribute once , So if it's an odd number , Then the answer is this interval .

Code ：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

int T,n,m,k;
int va[N];

int check(int l,int r)
{
    
	cout<<"? "<<l<<" "<<r<<"\n";
	cout.flush();
	int sum = 0;
	for(int i=l;i<=r;i++)
	{
    
		int x;
		cin>>x;
		if(x>=l&&x<=r) sum++;
	}
	return sum;
}

signed main()
{
    
	cin>>T;
	while(T--)
	{
    
		cin>>n;
		int l = 1,r = n;
		while(l<r)
		{
    
			int mid = (l+r)/2;
			if(check(l,mid)&1) r = mid;
			else l = mid+1;
		}
		cout<<"! "<<l<<"\n";
	}
	return 0;
}

summary ：
Think more , Accumulate experience .