Codeforces Round #719 Guess the K-th Zero (Hard version) - 线段树

题意

交互式问题。

有一个长度是$n$的由0和1构成数组。现在你每次可以查询任意区间的和。现在有$t$个提问，每个问题要你通过若干次查询后得出其中第$k$各0的位置。且每个提问之后，会把结果位置的0变为1。

限制是：你的查询数最多$6\cdot 10^4$。以及你必须输出上一个提问的结果后才会给你下一个$k$。

题解

根据easy version我们的思路一定是二分，不断查询$[1, mid]$的和。现在困难的地方是，每个提问之后，会把结果位置的0变为1。

立刻想到我们开一个Map，然后每次真正向系统查询的结果都放到map里。最后在一次提问结束之后更新一遍map里所有的结果。这样显然是会超时的。

于是我们想到维护一颗线段树来存储和更新查询的结果。我们定义2种更新和1种查询操作：

1. 根据对系统的查询，更新某一个具体位置的值，并且标记当前$mid$为已查询过。且强制忽略并清空这个位置的懒操作。
2. 对整个$[ans, n]$所有已存在的查询结果$+1$。
3. 查询某一个具体位置的值。

实现细节

定义线段树的节点：

static class Node {
    int left, right, value = -1;
    int plus = 0;
    boolean flag = false;
}

• left, right表示当前节点的区间。
• value表示查询的结果，如果left != right，则value的值没有意义。
• plus表示当前区间内的所有查询结果都需要增加plus。
• flag表示这个位置是否被查询过，如果left != right则这个值没有意义。

懒操作的下放：

private static void push_down(int p) {
    if (nodes[p].plus != 0) {
        nodes[p * 2].plus += nodes[p].plus;
        nodes[p * 2 + 1].plus += nodes[p].plus;
        nodes[p].plus = 0;
    }
}

具体操作的时候需要注意：

1. 对于点更新，由于是最新的向系统查询到的结果。因此下放的懒操作在这一个点上要直接忽略。
2. 对于查询点来说，如果这个点之前没有查过。那么不论懒操作是多少，都应该返回-1（表示没有缓存）。

代码