题目链接：https://codeforces.com/contest/1856/problem/D
大致题意：
这是一道交互题，有1~n的排列p，对于每次询问，你可以花费（R-L）2的代价去得到区间【L，R】之内的逆序对的个数，
你需要在5n2的代价内得到n的位置。
初步思路：
首先我们来思路，在什么时候，我们可以确定那个位置是n。
假设n的位置是p，那么我们可以知道
1：区间[l，p-1]和区间[l，p]的逆序对的个数是一样。因为p之前没有比n大的数。
2：区间[l，p+1]，[l，p+2]，，，，[l，n]他们的逆序对至少比前面多1。因为p的位置是n，所以每次至少会产生一个逆序对。
所以我们可以知道一个区间【L，R】的最大值定理，对于【L，R】，我们询问【L，L+1】，【L，L+2】，，，【L，R】，最后一个不增加的位置就是最大值所在处；
所以我们可以有一个暴力的想法，那就是枚举【1，2】，【1，3】，，，，【1，n】，最后不增加的位置就是n的位置。
但是，显然，这是过不了这道题的，他的代价为，1^2+2^2+....+(n-1)^2，接近n^3。
我们考虑一下怎么优化，想到求解逆序对的时候我们用到了分治，所以我们思考分治：
把区间 [l,r]分成 [l,mid]和 [mid+1,r]两个区间，分别求出两个区间的最大值位置pl,pr，然后根据最大值定理，在这两个待选位置中求出整个 [l,r]的最大值位置。
具体方法就是层层递归分治，合并时判断 pr是否是区间[l,pr] 的最大值位置，如果是，由于分治说明了pr是区间[mid+1，r]最大值位置，则整个[l,r]的最大值位置就是 pr，否则，最大值位置就是 pl。
代价复杂度为：4n2，所以是可以通过的。
代码：
#include<bits/stdc++.h>
int ask(int L, int R) {
if (L == R)return 0;
std::cout << "? " << L << " " << R << std::endl;
std::cin >> L;
return L;
}
int GO(int L, int R) {
if (R == L)return L;
int mid = (R + L) / 2;
int ansl = GO(L, mid), ansr = GO(mid + 1, R);
int pre = ask(ansl, ansr - 1), suf = ask(ansl, ansr);
return pre == suf ? ansr : ansl;
}
signed main() {
int T;
std::cin >> T;
while (T--) {
int n;
std::cin >> n;
int ans = GO(1, n);
std::cout << "! " << ans << std::endl;
}
return 0;
}
可以看出，码量很短，是一道很妙的思维题呢！
标签：890,位置,Institute,最大值,supported,mid,int,区间,逆序 From： https://www.cnblogs.com/ACMER-XiCen/p/17645272.html