[数据结构与算法]Codeforces Round #803 (Div. 2) VP补题

D. Fixed Point Guessing

大意：
有一个1-n的升序排序，从中选n-1/2对不相交的数字进行交换，会有一个数字是没有动的。

操作过后会得到一个最终序列。

交互问题。每次询问l,r，返回最终序列的l到r元素的升序排列

15个问题内找到没有改变位置的元素

思路:

做倒是做出来了，只是过程有点艰辛。。。（又是读不懂题的一天

n的范围有1e4那么大，但是只能问15个问题，差不多就是1/log的级别，那么自然就可以想到二分.

每次处理一个区间的话，就可以将区间分成两个部分，不妨先查左半部分，如果左半部分没问题，就意味着我们的答案在右半部分。

现在唯一的问题就是如何判断一个区间有没有问题了。

不妨定义一个元素对于一个区间是合法的，如果它的元素值满足val>=l&&val<=r。

现在考察我们的区间，在该区间内合法的元素，它只有两种情况：
1.它没有交换过，这个就是我们需要的答案。

2.它交换了，但是它仍在区间内，所以它是与区间内的另一个元素交换的，从这我们可以看出，交换过的合法元素一定是成对的。

所以：

如果当前区间内的合法数字有奇数个，那就一定是若干对交换的合法元素和一个答案，我们再对这个区间进行二分就可以了。如果有偶数个的话，那么久说明答案再另一个区间了。

最后区间范围变成1的时候，那个值就是答案。

#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;
}

（不知道为啥，总感觉交互题比普通题更有意思。。。）

?