CF1856D More Wrong

这道题目是一道关于使用分治算法求逆序对个数的问题。具体思路为：通过二分得到区间中两个部分的最大数位置，然后判断这两个数哪个更大，从而解决问题。

题意

有一个长度为 $n$ 的未知序列，询问 $l,r$ 可以通过花费 $r-l$ 个金币获取 $l$ 到 $r$ 之间逆序对的个数。你需要花费不多于 $5n^2$ 个金币来找到序列中最大数的个数。

思路

用分治来解决。如果询问的区间长度小于等于 $2$，很容易通过至多一次询问找到小区间中的最大数位置，否则二分后向下分治。这样，我们可以得到一个区间两个部分的最大数位置 $maxl,maxr$，问题变成如何判断这两个数哪个更大。

考虑区间 $[maxl,maxr]$，$maxl,maxr$ 之中对应数最大的那个显然也会是这个区间中的最大数。如果 $maxr$ 对应的数是区间中的最大数，那么区间 $[maxl,maxr]$ 中逆序对的数量会和 $[maxl,maxr-1]$ 中逆序对的数量相同。否则 $maxl$ 对应的数是区间中的最大数。

代码

int n;
int query(int l, int r) {
    if (l == r)
        return 0;
    cout << "? " << l << " " << r << endl;
    cout.flush();
    int x;
    cin >> x;
    return x;
}
int f(int l, int r) {
    if (l == r)
        return l;
    if (l + 1 == r) {
        int x = query(l, r);
        if (x)
            return l;
        else
            return r;
    }
    int maxl = f(l, (l + r) / 2), maxr = f((l + r) / 2 + 1, r);
    if (query(maxl, maxr) == query(maxl, maxr - 1))
        return maxr;
    else
        return maxl;
}
void solve() {
    cin >> n;
    int res = f(1, n);
    cout << "! " << res << endl;
    cout.flush();
}