题意
多组输入：{
每组给出一个n，有一个长度为n的数列，在开始的时候a i = i ，有三个数i , j , k
数列反转了 [i,j−1] [j,k]
要求出这三个数，可以对系统进行询问 [ l , r ] 区间内 逆序对 的个数，会返回这个值
}
思路：
对于这个反转之后的数列来说，[ 1 , i ] 之内的逆序对的个数为0
所以在左端点固定（= 1）的情况下，二分右端点找到这个i ii
然后对于一段反转之后的数列：
5 4 3 2 1
逆序对数量：
0 1 2 3 4
假如去掉前面的5
那么就为
0 1 2 3
两个做差发现值为4,+1就可以得到逆转的长度为5
所以说：
j = ask(i,n) - ask(i+1,n) + 1 + i; k = j + ask(j,n) - ask(j+1,n);
而在二分左端点l ll的过程也不会很大，问题解决
ac_code:
ll ask(ll l,ll r){ ll sysin = 0; cout <<"? " << l << ' ' << r << endl; cout.flush(); cin >> sysin; return sysin; } int main() { int _ = read; while(_ --){ ll n = read; ll l = 1,r = n; ll i,j,k; i = j = k = 0; while(l < r) { ll mid = l+r >> 1; if(ask(1,mid)) r = mid; else l = mid + 1; } i = l - 1; j = ask(i,n) - ask(i+1,n) + 1 + i; k = j + ask(j,n) - ask(j+1,n); cout << "! " << i << ' ' << j << ' ' << k << endl; cout.flush(); // printf("! %lld %lld %lld\n",i,j,k); } return 0; }
