526互联

Codeforces Round 890 (Div. 2) supported by Constructor Institute D. More Wrong（交互，分治）

发布时间 2023-08-27 19:54:32作者: XiCen

题目链接：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;
}

 

可以看出，码量很短，是一道很妙的思维题呢！

​