Sengxian's Blog

题目地址

描述

给定一个含有 $n$ 个数的序列 $a_1, a_2, a_3,...,a_n$，程序必须回答这样的询问：对于给定的 $i,j,k$，在$a_i, a_{i + 1}, a_{i + 2},...,a_j$ 中第 $k$ 小的数是多少 $(1\le k\le j-i+1)$，并且，你可以改变一些 $a_i$ 的值，改变后，程序还能针对改变后的 $a$ 继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列 $a$，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 第一行有两个正整数 $n(1\le n\le 10000)$，$m(1\le m\le 10000)$。分别表示序列的长度和指令的个数。第二行有 $n$ 个数，表示 $a_1, a_2, a_3,...,a_n$，这些数都小于 $10^9$。接下来的 $m$ 行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t（$i,j,k$ 是数字，$1\le i\le j \le n, 1\le k \le j-i+1$）表示询问指令，询问 $a_i, a_{i + 1}, a_{i + 2},...,a_j$ 中第 $k$ 小的数。C i t 表示把 $a_i$ 改变成为 $t$。

样例输入

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

样例输出

3
6

分析

整体二分，貌似关于整体二分的资料很少，其中提到细节的又是少之又少，我仔细的说一下这个题，争取让没学过整体二分的也能看懂。
我们首先考虑一个询问 $Q$： Q l r k，询问区间 $[l, r]$ 的第 $k$ 小。能够影响这个询问的只有：

1. 序列的初始值
2. 在这个询问之前的修改

我们强行用二分解决这个询问，可以吗？可以。用如下办法解决这个询问：

1. 二分答案 $mid$，当前答案区间 $[l, r)$。
2. 遍历在之前 $Q$ 的所有的修改并执行，找到 $[a, b]$ 之间 $mid$ 是第 $t$ 小。
3. 如果 $t \le k$，则令：$l = m$，否则令 $r = m$。原因是要找到最后一个排名小于等于 $k$ 的数，它就是第 $k$ 小。

直到 $r - l = 1$，那么 $l$ 便是答案。考虑第 2 步的实现，可以手动修改，然后统计，但这样并不好，不利于我们接下来的整体二分。
在平衡树的学习中我们就发现，修改一个节点的值并不是一件容易的事情，那么我们就先删除再插入。在这里我们用类似的技巧，对于一个修改，我们减去原有的值，加上修改成的值。
我们把序列的初始值也看作是修改，在时间上放在最前面，则序列的初始值全是 $0$，那么每个位置的初始值 $a_i$ 看作加上 $a_i$；将 $a_i$ 修改为 $v$，可以看作将位置 $i$ 减去 $a_i$，再加上 $v$。
统计数 $mid$ 的排名，只需统计有多少个数小于 $mid$，加上 1 便是排名。我们开一个树状数组，长度为 $n$，每一位表示位置 $i$ 是否小于 $mid$。那么碰到一个增加的值 $v$，如果 $v < mid$，那么位置 $i$ 就加 $1$，如果碰到一个减去的值 $v$，如果 $v < mid$，那么位置 $i$ 就减去 $1$。最后树状数组 $[a, b]$ 内的和 + 1 就是 $mid$ 的排名。假设在 $Q$ 之前有 $m$ 个询问，这样做的复杂度是 $O(m\log n)$ 的。
于是如果对于所有的询问都采取这个方法，我们得到 $O(m^2\log n)$ 的算法，显然不行。

每次二分一个询问太少了，能不能一次二分多个询问呢？可以。
我们假定函数 Solve(Q, l, r) 可以解决问题，其中 $Q$ 是操作队列（包含增加，减少，查询操作，按照时间先后顺序），$[l, r)$ 是所有查询操作可能的取值范围。如果 $Q_0$ 是我们的所有操作的话（别忘了初始值算增加操作），那么函数 Solve(Q0, 0, 1e9 + 1) 显然可以解决问题。
整体二分的精髓就在于他一次可以对多个查询操作进行二分。我们来看 Solve(Q, l, r) 的执行过程：

1. 如果 $Q$ 为空，退出；如果 $l + 1 = r$, 给 $Q$ 中所有的查询操作赋值 $l$。退出。
2. 令 $mid = (l + r) / 2$，新建队列 $Q_1, Q_2$。
3. 遍历 $Q$：
   • 如果遇到一个增加操作 i v，如果 $v < mid$，那么树状数组位置 $i$ 就加 $1$，操作入队 $Q_1$，否则入队 $Q_2$；
   • 如果遇到一个减少操作 i v，如果 $v < mid$，那么树状数组位置 $i$ 就减去 $1$，操作入队 $Q_1$，否则入队 $Q_2$；
   • 如果遇到查询 a b k，查询区间 $[a, b]$ 的和 $t$，如果 $t\le k$，操作入队 $Q_1$；否则 $t = t - k$，操作入队 $Q_2$。
4. 再次遍历 $Q$，将之前 +1 的地方全部 -1，之前 -1 的地方全部 +1，目的是清空树状数组。（千万不能 memset，这样导致我们每次 solve 都与 $n$ 有关，这样的复杂度我们承受不了！ ）
5. solve(Q1, l, mid) 以及 solve(Q_2, mid, r)。

看到这里，或许你还很迷糊，其实不难理解，这是一次二分的过程，不过是将很多查询一起二分的：对于一个询问的每次二分，我们顺序执行它前面的所有操作，可以得到缩小解的范围。注意到其实在一个询问之前不只有修改，可能还有别的询问，我们掠过了这些操作，非常浪费，如果我们一次二分多个询问的话，那么我们就可以批量缩小每个询问的解的范围。
显然，值大于等于 $mid$ 的操作对答案在 $[l, mid)$ 中的询问没有影响，所以我们把值小于 $mid$ 的操作和答案在 $[l, mid)$ 中的询问直接丢到 $Q_1$ 里面递归解决。
那答案在 $[mid, r)$ 中的询问怎么办？值小于 $mid$ 的操作会对其造成影响，为什么不丢到 $Q_2$ 里面去？不可否认，值小于 $mid$ 的操作会对其造成影响，但对答案在 $[mid, r)$ 中的询问造成的影响是一样的！所以我们直接减去 $k$，相当于执行了所有值小于 $mid$ 的操作！再递归解决。

这个题大概就是这样，细节是很重要的，整体二分的过程，在不断的分离操作，不断的缩小解的范围，达到求解的目的。

代码

//  Created by Sengxian on 4/1/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1901 整体二分，带修改区间第 K 大
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <queue>
#define mid (((l) + (r)) / 2)
#define lowbit(x) (x & (-x))
using namespace std;

inline int ReadInt() {
    static int ch, n;
    ch = getchar(), n = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

struct oper {
    int type, idx, l, r, k;
}t;

const int maxn = 10000 + 3, maxm = 10000 + 3;
int c[maxn], a[maxn], ans[maxm], n, m, cnt = 0;

inline void add(int x, int v) {
    x++;
    while (x <= n) {
        c[x] += v;
        x += lowbit(x);
    }    
}
inline int sum(int x) {
    x++; int ret = 0;
    while (x > 0) {
        ret += c[x];
        x -= lowbit(x);
    }
    return ret;
}

//操作序列，答案区间 [l, r)
void solve(queue<oper> &q, int l, int r) {
    if (q.empty()) return;
    if (l >= r) return;
    if (r - l == 1) {
        while (!q.empty()) {
            t = q.front(); q.pop();
            if (t.type == 3) ans[t.idx] = l;
        }
        return;
    }
    queue<oper> q1, q2;
    queue<int> idp, idn;
    while (!q.empty()) {
        t = q.front(); q.pop();
        if (t.type == 1) {
            if (t.k < mid) add(t.idx, 1), idp.push(t.idx), q1.push(t);
            else q2.push(t);
        }else if (t.type == 2) {
            if (t.k < mid) add(t.idx, -1), idn.push(t.idx), q1.push(t);
            else q2.push(t);
        } else {
            int v = sum(t.r) - sum(t.l - 1);
            if (v + 1 <= t.k) t.k -= v, q2.push(t);
            else q1.push(t);
        }
    }
    while (!idp.empty()) {
        add(idp.front(), -1);
        idp.pop();
    }
    while (!idn.empty()) {
        add(idn.front(), 1);
        idn.pop();
    }
    solve(q1, l, mid);
    solve(q2, mid, r);
}

char str[2];
int main() {
    queue<oper> q;
    n = ReadInt(), m = ReadInt();
    //type 1 +
    //type 2 -
    //type 3 Query
    for (int i = 0; i < n; ++i) {
        t.type = 1, a[i] = t.k = ReadInt();
        t.idx = i;
        q.push(t);
    } 
    for (int i = 0; i < m; ++i) {
        scanf("%s", str);
        if (str[0] == 'Q') {
            t.type = 3, t.l = ReadInt() - 1, t.r = ReadInt() - 1, t.k = ReadInt(), t.idx = cnt++;
            q.push(t);
        } else if (str[0] == 'C') {
            t.type = 2, t.idx = ReadInt() - 1, t.k = a[t.idx];
            q.push(t);
            t.type = 1, a[t.idx] = t.k = ReadInt();
            q.push(t);
        }
    }
    memset(c, 0, sizeof c);
    solve(q, 0, 1e9 + 3);
    for (int i = 0; i < cnt; ++i)
        printf("%d\n", ans[i]);
    return 0;
}