题意
交互式问题。
有一个长度是$n$的由0和1构成数组。现在你每次可以查询任意区间的和。现在有$t$个提问，每个问题要你通过若干次查询后得出其中第$k$各0的位置。且每个提问之后，会把结果位置的0变为1。
限制是：你的查询数最多$6\cdot 10^4$。以及你必须输出上一个提问的结果后才会给你下一个$k$。
题解
根据easy version我们的思路一定是二分，不断查询$[1, mid]$的和。现在困难的地方是，每个提问之后，会把结果位置的0变为1。
立刻想到我们开一个Map，然后每次真正向系统查询的结果都放到map里。最后在一次提问结束之后更新一遍map里所有的结果。这样显然是会超时的。
于是我们想到维护一颗线段树来存储和更新查询的结果。我们定义2种更新和1种查询操作：
- 根据对系统的查询，更新某一个具体位置的值，并且标记当前$mid$为已查询过。且强制忽略并清空这个位置的懒操作。
- 对整个$[ans, n]$所有已存在的查询结果$+1$。
- 查询某一个具体位置的值。
实现细节
定义线段树的节点：
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（表示没有缓存）。
代码
Submission #115345090 - Codeforces
Codeforces. Programming competitions and contests, programming community
