Cfdiv2 Fixed Point Guessing - (2 points for Interval answer)

D

Titre：
C'est juste pour toi1ÀnTableau de,Mais ça s'est passén+1/2Sous - échange,Chaque numéro n'est échangé qu'une seule fois,Donc un seul nombre n'a pas été échangé.Alors vous pouvez demander15Une fois,Un intervalle à la fois,Vous renvoie le nombre de cet intervalle de petit à grand après l'arrangement.Maintenant, demandez - vous quel nombre n'a pas été échangé.

Penser：
J'ai commencé à voir15Je savais que c'était deux points,Mais je pensais que oui.dfsDeux points,Chaque jugement récursif.Mais je ne me sens pas très bien pour écrire.En fait,Pour deux points,Vous pouvez diviser la réponse en deux parties dans quelle plage.C'est - à - dire juger d'abordlÀr,Si la réponse est là,r = mid.Sinonl = mid+1.C'est - à - dire dans l'autre section.C'est un simple jugement dans quelle section,Il n'y a pas de réponse, mieux c'est, pire c'est.Mais comment juger,En fait,,Nombre d'entréesx,SixInlÀrÀ l'intérieur,Ça veut dire qu'il l'a échangé contre,Alors les nombres apparaîtront deux fois,Sinon, c'est0Une fois.Mais quel nombre sans échange contribue une fois,Donc si c'est un nombre impair,Alors la réponse est cette section.

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

Résumé：
Réfléchis.,Accumuler de l'expérience.