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(表示没有缓存)。

代码

Submission #115345090 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论