[BZOJ1901] 带修区间第k小

论暴力如何摩擦正解

本文介绍的并非正解,而是高效的暴力

Description

给定一个含有n个数的序列$a[1],a[2],a[3]……a[n]$,程序必须回答这样的询问:对于给定的i,j,k,在$a[i],a[i + 1],a[i + 2]……a[j]$中第k小的数是多少($1 ≤ k ≤ j - i + 1$),并且,你可以改变一些$a[i]$的值,改变后,程序还能针对改变后的a继续回答上面的问题.

Format

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

$Q\,i\,j\,k$
或者
$C\,i\,t$

$Q\,i\,j\,k$ (i,j,k是数字,$1≤i≤j≤n$, $1≤k≤j-i+1$)
表示询问指令,询问$a[i],a[i+1]……a[j]$中第k小的数.
$C\,i\,t$ ($1≤i≤n$,$0≤t≤10^9$)表示把$a[i]$改变成为t

Sample

Input

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

Output

1
2
3
6

DataSize

In Format

Analyze

哦这不是主席树套(线段树/树状数组)的板子嘛
所以不能这样打

我要分块

具体方法如下:

  • 将数列分块,并对每个块排序
  • 二分最小值,再二分每个区间内比它大的最小的数的位置,因为块内有序所以可以求出块内对排名的贡献
  • 修改需要对所在块重新sort,(复杂度可以更优不过意义不大)
  • 准备好足够的时间来调试你的分块!

以下是分块代码!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <algorithm>
#include <cmath>
#define RI register int
#define Min(x,y) (x) > (y) ? (x) = (y) : 0
#define Max(x,y) (x) < (y) ? (x) = (y) : 0

using namespace std;

const int maxn = 100005;
int blk1[maxn], blk2[maxn], n, m, siz, mi = 1e9, mx = -1, l, r, k;
char q[10];

inline void Query(RI L, RI R, RI K) {
RI ll = L / siz, rr = R / siz, mid = 0, num = 0, ls = mi, rs = mx;
while (ls <= rs) {
mid = (ls + rs) >> 1, num = 0;
if (ll == rr) {
for (RI i = L; i <= R; ++i) if (blk1[i] < mid) ++num;
}
else {
for (RI i = L; i < siz * (ll + 1); ++i) if (blk1[i] < mid) ++num;
for (RI i = ll + 1; i < rr; ++i) num += lower_bound(blk2 + i * siz, blk2 + (i + 1) * siz, mid) - (blk2 + i * siz);
for (RI i = siz * rr; i <= R; ++i) if (blk1[i] < mid) ++num;
}
if (num < k) ls = mid + 1;
else rs = mid - 1;
}
printf("%d\n", ls - 1);
return;
}

inline void Modify(RI u, RI K) {
RI ll = u / siz * siz, rr = min((u / siz + 1) * siz, n);
blk1[u] = k, Min(mi, k), Max(mx, k);
for (RI i = ll; i < rr; ++i) blk2[i] = blk1[i];
sort(blk2 + ll, blk2 + rr);
return;
}

int main() {
scanf("%d%d", &n, &m), siz = sqrt(n + 1.);
for (RI i = 0; i < n; ++i) scanf("%d", blk1 + i), blk2[i] = blk1[i], Min(mi, blk1[i]), Max(mx, blk1[i]);
for (RI i = 0; i < n; i += siz) sort(blk2 + i, blk2 + min(i + siz, n));
while (m--) {
scanf("%s", q);
if (q[0] == 'Q') scanf("%d%d%d", &l, &r, &k), Query(l - 1, r - 1, k);
else scanf("%d%d", &l, &k), Modify(l - 1, k);
}
}

Helping poor children in CSSYZ!!!