Codeworks round 803 (Div. 2) VP supplement

D. Fixed Point Guessing

Carelessness ：
There is one 1-n In ascending order , Choose from n-1/2 Exchange disjoint numbers , There will be a number that doesn't move .

After the operation, you will get a final sequence .

Interaction problem . Every time I ask l,r, Returns the... Of the final sequence l To r The ascending order of elements

15 The element that has not changed its position was found in the question

Ideas :

It's done , It's just a little hard ...（ Another day when I can't read the questions

n What is the scope 1e4 So big , But I can only ask 15 A question , Almost 1/log The level of , Then naturally, you can think of two points .

If you deal with an interval at a time , The interval can be divided into two parts , You might as well check the left half first , If the left half is ok , That means our answer is in the right half .

Now the only problem is how to judge whether there is a problem in an interval .

You can define that an element is legal for an interval , If its element value satisfies val>=l&&val<=r.

Now look at our interval , Legal elements in this interval , There are only two cases of it ：
1. It has not been exchanged , This is the answer we need .

2. It's swapped , But it is still within the range , So it is swapped with another element in the interval , We can see from this , The legal elements exchanged must be in pairs .

therefore ：

If there are odd legal numbers in the current interval , It must be some pairs of legal elements of exchange and an answer , Let's divide this interval by two . If there are even numbers , So long, it means that the answer is in another range .

Finally, the range becomes 1 When , That value is the answer .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+10;
ll n,m,k;
ll t;
ll a;
ll mas[N];
void cx(ll l,ll r)
{
	if(l==r)
	{
		std::cout<<"? "<<l<<' '<<r<<endl;
		cin>>a;
		std::cout<<"! "<<a<<endl;
		return;
	}
	ll mid=l+r>>1;
	ll cnt=0;
	std::cout<<"? "<<l<<" "<<mid<<endl;
	for(int i=1;i<=mid-l+1;++i) std::cin>>mas[i];
	for(int i=1;i<=mid-l+1;++i)
	{
		if(mas[i]>=l&&mas[i]<=mid) cnt++; 
	} 
	if(cnt%2)
	{
		cx(l,mid);
	}
	else cx(mid+1,r);
}
void solve()
{
	std::cin>>n;
	cx(1,n);
}
int main()
{//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	std::cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

（ I don't know why , I always feel that interactive questions are more interesting than ordinary questions ...）