BZOJ1901 Dynamic Rankings <整体二分>

Problem

Dynamic Rankings

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

给定一个含有$n$个数的序列$a[1],a[2],a[3],\cdots,a[n]$。
对于给定的$i,j,k$，请回答在$a[i],a[i+1],a[i+2],\cdots,a[j]$中第$k$小的数是多少$(1\le k\le j-i+1)$。
在询问中会有操作改变一些$a[i]$的值，改变后，需要针对改变后的$a$继续回答上面的问题。

Input

第一行有两个正整数$n,m$。
分别表示序列的长度和指令的个数。
第二行有$n$个数，表示$a[1],a[2]\cdots,a[n]$，这些数都小于$10^9$。
接下来的$m$行描述每条指令，每行的格式是下面两种格式中的一种。

• $Q\;i\;j\;k\;(1\le i\le j\le n,1\le k\le j-i+1)$表示询问指令，询问$a[i],a[i+1],\cdots,a[j]$中第$k$小的数。
• $C\;i\;t\;(1\le i\le n,0\le t\le10^9)$表示把$a[i]$改变成为$t$。

Output

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input

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

Sample Output

3
6

HINT

$n,m\le10^4$

标签：整体二分

Solution

整体二分经典题，直接上整体二分即可。

考虑将所有询问离线下来，对所有询问同时进行二分答案，二分函数有四个参数$l,r,s,t$，表示答案在$[s,t]$区间内的询问为在询问序列上位置在$[l,r]$之间的所有询问。
如果$s=t$，则可知询问序列上位置在$[l,r]$间的所有询问答案均为$s$。否则，我们需要把$[l,r]$间的所有询问分为前后两部分，前一部分为答案在$[s,\frac{s+t}{2}]$间的所有询问，后一部分为答案在$[\frac{s+t}{2}+1,t]$间的所有询问。这个过程用一棵树状数组判断一下$[l,r]$间每个询问的答案在哪边即可。
然而我们还需要维护修改操作。对于修改操作，我们同样将其加入整体二分。当询问函数将答案限制到$[s,t]$时，只有参数$t$在$[s,t]$间的修改操作才会对这个$[l,r]$间的询问答案产生影响。于是将每个修改拆成两个操作，即在某位置上删除一个数和加入一个数。
用树状数组维护时，若删除或加入的数在$[s,\frac{s+t}{2}]$间，在树状数组上对应位置$-1$或$+1$。对于询问，若询问区间为$[tl,tr]$，那么该询问的$num$值为树状数组上$[tl,tr]$位置上的值之和。这样一来，$num$统计的是每个询问区间内小于等于$\frac{s+t}{2}$的数的个数，若$num\ge k$，则答案一定在$[s,\frac{s+t}{2}]$间；否则，答案一定大于$\frac{s+t}{2}$。分治处理即可。

由于整体二分会带来一个$\log{n}$，枚举每个询问并用树状数组判断其答案在左边还是右边需要$n\log{n}$，故总复杂度为$O(n\log^{2}{n})$。

Code

#include <bits/stdc++.h>
#define MAX_N 20000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int N, M, Q, cnt, val[MAX_N+5], ans[MAX_N+5];
struct node {int id, tp, a, b, k, s;} p[MAX_N+5], q[MAX_N+5];
int num[MAX_N+5], tr[MAX_N+5]; bool mrk[MAX_N+5];
void inc(int p) {for (; p <= N; p += (p&-p)) tr[p]++;}
void dec(int p) {for (; p <= N; p += (p&-p)) tr[p]--;}
int sum(int p) {int ret = 0; for (; p; p -= (p&-p)) ret += tr[p]; return ret;}
void bi_solve(int l, int r, int s, int t) {
    if (l > r) return;
    if (s == t) {
        for (int i = l; i <= r; i++)
            if (p[i].tp == 3) ans[p[i].id] = s;
        return;
    }
    for (int i = l; i <= r; i++)
        if (p[i].tp == 1 && p[i].b <= mid) inc(p[i].a);
        else if (p[i].tp == 2 && p[i].b <= mid) dec(p[i].a);
        else if (p[i].tp == 3) num[i] = sum(p[i].b)-sum(p[i].a-1);
    for (int i = l; i <= r; i++)
        if (p[i].tp == 1 && p[i].b <= mid) dec(p[i].a);
        else if (p[i].tp == 2 && p[i].b <= mid) inc(p[i].a);
    int lsz = 0;
    for (int i = l; i <= r; i++)
        if (p[i].tp == 3) {
            if (p[i].k <= p[i].s+num[i]) lsz++, mrk[i] = false;
            else p[i].s += num[i], mrk[i] = true;
        } else lsz += (p[i].b <= mid), mrk[i] = (p[i].b > mid);
    for (int i = l, p1 = l, p2 = l+lsz; i <= r; i++)
        if (!mrk[i]) q[p1++] = p[i]; else q[p2++] = p[i];
    for (int i = l; i <= r; i++) p[i] = q[i];
    bi_solve(l, l+lsz-1, s, mid), bi_solve(l+lsz, r, mid+1, t);
}
int main() {
    read(N), read(M);
    for (int i = 1; i <= N; i++)
        read(val[i]), p[++cnt] = (node){0, 1, i, val[i], 0, 0};
    for (int i = 1, a, b, k; i <= M; i++) {
        char opt[2]; scanf("%s", opt);
        if (opt[0] == 'C')
            read(a), read(b), 
            p[++cnt] = (node){0, 2, a, val[a], 0, 0}, 
            p[++cnt] = (node){0, 1, a, (val[a] = b), 0, 0};
        else
            read(a), read(b), read(k), 
            p[++cnt] = (node){++Q, 3, a, b, k, 0};
    }
    bi_solve(1, cnt, 0, INF);
    for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
    return 0;
}