CF2163D2 D2. Diadrash (Hard Version)题解

D2. Diadrash (Hard Version)

题目翻译

​ 这是一道交互题，题目中有一个隐藏的排列，我们得到了q组询问，每组询问[l, r]，我们需要求出所有询问中MEX[l, r]最大的是多少，我们可以进行提问 ? l r，交互其会返回区间[l, r]的MEX。我们需要在30次询问内找出答案。排列长度n <= 1e4, 询问q <= 3e5。

思路

​ 首先本题根据MEX的性质，我们不难发现所有被完全包含的区间都没有意义，所以我们对区间进行区去包含的处理，此时最多只会剩下n个区间询问。我们要解决hard版的30次询问还需要注意到MEX的另外一个重要性质，对于MEX[l, r] = min(MEX[1, r], MEX[l, n])，这个性质的证明考虑第一个不在MEX[l, r]中的数位于其左侧或右侧就可以简单证明得到。

​ 我们对去重后的区间按左端点进行排序，我们可以对这些区间进行二分，因为去了包含之后的区间一定满足l[i] < l[i + 1], r[i] < r[i + 1]。对于我们当前验证的区间media，若其为[l, r],我们记a = MEX[1, r], b = MEX[l, n]，若a < b，则我们只有考虑media区间右侧的区间即可，因为此时我们需要让r变大才有可能使得MEX[l, r]更大。若a > b同理，所以我们可以二分缩小一半的可能（带来更大答案的区间只可能在一个半边），故解法成立，询问次数 2 * lg(n) <= 30。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int ask(int l, int r){
    std::cout << "? " << l << space << r << std::endl;
    int ans;
    std::cin >> ans;
    return ans;
}

void solve(){
    int n, q;
    std::cin >> n >> q;
    int mid = (n + 1) / 2;
    std::vector<int> lpos(n + 1, 0);
    for(int i = 1; i <= q; i++){
        int l, r;
        std::cin >> l >> r;
        lpos[l] = std::max(lpos[l], r);
    }
    int r_get = 0;
    std::vector<std::pair<int, int>> qu;
    for(int i = 1; i <= n; i++){
        if(lpos[i] > r_get){
            qu.push_back({i, lpos[i]});
            r_get = lpos[i];
        }
    }

    int ans = 0;
    int left = 0;
    int right = qu.size() - 1;
    while(left <= right){
        int media = (left + right) / 2;
        int l = qu[media].ff;
        int r = qu[media].ss;
        int a = ask(1, r);
        int b = ask(l, n);
        ans = std::max(ans, std::min(a, b));
        if(a < b){
            left = media + 1;
        }
        else{
            right = media - 1;
        }
    }
    std::cout << "!" << space << ans << std::endl;
}