K-th Number

题目描述

给定长度为n的序列A,对于m个形式为(i,j,k)的询问,输出序列A中下标为[i,j]的区间内第k大的数.加强版支持修改
$(1 \le n \le 100000, 1 \le m \le 5000)$

简化版

题目描述

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, **given an array a[1…n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: “What would be the k-th number in a[i…j] segment, if this segment was sorted?” **
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2…5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

The first line of the input file contains n — the size of the array, and m — the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
The second line contains n different integer numbers not exceeding 109 by their absolute values — the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).

For each question output the answer to it — the k-th number in sorted a[i…j] segment.

离线分治代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
inline int lowbit(int x) { return x & (-x);}
int ask(int x){ int ANS = 0; for(; x; x -= lowbit(x)) ANS += coun[x]; return ANS;}
void add(int x, int y){ for(; x <= n; x += lowbit(x)) coun[x] += y;}

ASK L[200100], R[200100];
//因为最后的赋值会导致a数组动态变化所以不能用int类型的数组来简单存储下标
void CDQ(int l, int r, int s, int e){
//哎呀其实这里好像不是CDQ来着
//应该叫"基于值域的整体二分"
//但是因为刚学了CDQ所以分不太清...
if(s > e) return;//递归终止条件
if(l == r){//容易理解但是不容易想到啊
for(int i = s; i <= e; ++ i)
if(a[i].ty) ans[a[i].ty] = l;
return;//return终止也能漏掉真是醉了...
}
int mid = (l + r) >> 1;
int lt = 0, rt = 0;
for(int i = s; i <= e; ++ i){
//所以说这里是按照时间序进行排序的
if(a[i].ty){
int CNT = ask(a[i].r) - ask(a[i].l - 1);
if(CNT >= a[i].k) L[++ lt] = a[i];
//如果值<=mid的数字在区间内的数量大于a[i].k,说明排在第k位的数字要比mid要小
//那么就要把这个操作放到值域属于[l,mid]的下一步更加精准的查询里
//反之亦然
else {
a[i].k -= CNT;//*
R[++ rt] = a[i];
}
}else {
if (a[i].k <= mid) add(a[i].l, 1), L[++ lt] = a[i];
//小于等于mid的数都要算入总贡献之中
//大概可以类比于splay查找?
else R[++ rt] = a[i];//大于mid的不去管它
}
}
for(int i = s; i <= e; ++ i) if(!a[i].ty && a[i].k <= mid) add(a[i].l, -1);
//回溯清空树状数组方便下次使用
for(int i = 1; i <= lt; ++ i) a[s + i - 1] = L[i];
for(int i = 1; i <= rt; ++ i) a[s + lt + i - 1] = R[i];
CDQ(l, mid, s, s + lt - 1), CDQ(mid + 1, r, s + lt, e);
}

int main(){
n = read(), m = read();
for(int i = 1; i <= n; ++ i) a[i].k = read(), b[i] = a[i].k;
sort(b + 1, b + n + 1);
int len = unique(b + 1, b + n + 1) - b - 1;
//要记好离散化的板子啊
//注意是-b-1
for(int i = 1; i <= n; ++ i) {
a[++ cnt].k = lower_bound(b + 1, b + len + 1, a[i].k) - b;
a[cnt].l = i;
}
for(int i = 1; i <= m; ++ i) {
a[++ cnt].ty = i;
a[cnt].l = read(), a[cnt].r = read(), a[cnt].k = read();
}
CDQ(1, len, 1, cnt);
//出锅的主要原因在这里
//作死要用离散化然后又CDQ(b[1], b[n], 1, cnt);
//然后妥妥地RE了,最后查了超级久还下了数据才总算是查出来了
//心碎
for(int i = 1; i <= m; ++ i) printf("%d\n", b[ans[i]]);
//之前还犯傻加了一个反离散化的back数组...
return 0;
}

可持久化线段树代码

先离散化然后建树
信息是数列中有多少个数在值域$[l,r]$中
root[i]为根的树存储的是数列$1$ ~ $i$的信息
注意每棵树的值域都是完美对应的

这意味着:"$root[R_i]$的值域区间$[l,r]$的$cnt$值"减去"$root[L_i-1]$的值域区间$[l,r]$的$cnt$值"就等于$A[L_i$ ~ $R_i]$中有多少个数落在值域$[l,r]$内
— 《算法竞赛进阶指南》

lr都作为参数传入函数,节省空间

递归版

丢标程

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
//递归版的insert
//大概会比我的要慢一点?
int insert(int now, int l, int r, int x, int delta) {
int p = ++tot;
tree[p] = tree[now];
if (l == r) {
tree[p].sum += delta;
return p;
}
int mid = (l + r) >> 1;
if (x <= mid) tree[p].lc = insert(tree[now].lc, l, mid, x, delta);
else tree[p].rc = insert(tree[now].rc, mid + 1, r, x, delta);
tree[p].sum = tree[tree[p].lc].sum + tree[tree[p].rc].sum;
return p;
}

//主函数:
for (int i = 1; i <= n; i++) {
int x = lower_bound(b + 1, b + t + 1, a[i]) - b; // 离散化后的值
root[i] = insert(root[i - 1], 1, t, x, 1); // 值为x的数增加1个
}


//标程递归版的ask
//会比我写的好理解一些?
int ask(int p, int q, int l, int r, int k) {
if (l == r) return l; // 找到答案
int mid = (l + r) >> 1;
int lcnt = tree[tree[p].lc].sum - tree[tree[q].lc].sum; // 值在[l,mid]中的数有多少个
if (k <= lcnt) return ask(tree[p].lc, tree[q].lc, l, mid, k);
else return ask(tree[p].rc, tree[q].rc, mid + 1, r, k - lcnt);
}

主函数:
for (int i = 1; i <= m; i++) {
int l, r, k; scanf("%d%d%d", &l, &r, &k);
int ans = ask(root[r], root[l - 1], 1, t, k);
printf("%d\n", b[ans]); // 从离散化后的值变回原值
}
非递归版

感觉会比那种快一点啊
但是标程会好理解一点

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//对照标程改成了非递归版本
//但是初始化树也就是建立root=0的树这部分我还没想到是否有非递归的实现可能
int build(int l, int r){
int now = ++ cnt;
if(l == r) return now;
int mid = (l + r) >> 1;
tree[now].ls = build(l, mid);
tree[now].rs = build(mid + 1, r);
return now;//这个地方不能漏掉啊(哭泣
}

void insert(int i, int l, int r, int k){
int now = (root[i] = ++ cnt), ano = root[i - 1];
while(l < r){
tree[now].num = tree[ano].num + 1;
//其实上面递归版本的delta只能是1啊所以就全部加上1就好
int mid = (l + r) >> 1;
if(k <= mid) {
r = mid;
tree[now].ls = ++ cnt, tree[now].rs = tree[ano].rs;
now = cnt, ano = tree[ano].ls;
}else {
l = mid + 1;
tree[now].rs = ++ cnt, tree[now].ls = tree[ano].ls;
now = cnt, ano = tree[ano].rs;
}
}
//这里要注意 l == r 时我们已经退出了程序所以根节点还要特殊处理一下
++ tree[now].num;
}

int ask(int L, int R, int k){
int l = 1, r = len;
L = root[L - 1], R = root[R];
while(l < r){
int mid = (l + r) >> 1;
int cnt = tree[tree[R].ls].num - tree[tree[L].ls].num;
if(k <= cnt) {
R = tree[R].ls, L = tree[L].ls;
r = mid;
}else {
R = tree[R].rs, L = tree[L].rs;
l = mid + 1;
k -= cnt;
}
}
return l;
}

int main(){
n = read(), m = read();
for(int i = 1; i <= n; ++ i) a[i] = b[i] = read();
sort(b + 1, b + n + 1);
len = unique(b + 1, b + n + 1) - b - 1;
root[0] = build(1, len);
for(int i = 1; i <= n; ++ i)
insert(i, 1, len, lower_bound(b + 1, b + len + 1, a[i]) - b);
for(int i = 1, l, r, k; i <= m; ++ i){
l = read(), r = read(), k = read();
//这里之前作死写成printf("%d\n", b[ask(read(), read(), read())]);然后出锅了
//a b c的读入会变成c b a
//搞不清楚为什么
//总之要小心一点
printf("%d\n", b[ask(l, r, k)]);
}
return 0;
}

加强版

题目描述

给定一个含有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继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。

对于每一个询问指令,你必须输出正确的回答。
第一行有两个正整数n(1≤n≤100000),m(1≤m≤100000)。分别表示序列的长度和指令的个数。
第二行有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。

代码

加强版的代码其实就是简化版加了一丢丢修改

主函数

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
51
52
53
54
55
56
57
58
59
60
61
62
//再一次数组开小..
void CDQ(int l, int r, int s, int e){
if(s > e) return;
if(l == r){
for(int i = s; i <= e; ++ i)
if(a[i].ty > 0) ans[a[i].ty] = l;
return;
}
int mid = (l + r) >> 1;
int lt = 0, rt = 0;
for(int i = s; i <= e; ++ i){
if(a[i].ty > 0){
int CNT = ask(a[i].r) - ask(a[i].l - 1);
if(CNT >= a[i].k) L[++ lt] = a[i];
else {
a[i].k -= CNT;
R[++ rt] = a[i];
}
}else {
if (a[i].k <= mid) add(a[i].l, a[i].r), L[++ lt] = a[i];
//注意这里的r标记的是增加/删除操作
//要不要仔细理解一下这样做的正确性呢
else R[++ rt] = a[i];
}
}
for(int i = s; i <= e; ++ i) if(a[i].ty <= 0 && a[i].k <= mid) add(a[i].l, -a[i].r);
for(int i = 1; i <= lt; ++ i) a[s + i - 1] = L[i];
for(int i = 1; i <= rt; ++ i) a[s + lt + i - 1] = R[i];
CDQ(l, mid, s, s + lt - 1), CDQ(mid + 1, r, s + lt, e);
}

//依然作死要用离散化呢
int main(){
n = read(), m = read();
for(int i = 1; i <= n; ++ i) {
a[++ cnt] = ASK{0, i, 1, read()};
b[++ cntb] = num[i] = a[i].k;
//num:暂时储存数列的值
}
for(int i = 1; i <= m; ++ i) {
cin >> c;
if(c == 'Q'){
a[++ cnt] = ASK{i, read(), read(), read()};
}else{
//改变一个数相当于删去一个数再增加一个数
//这里就是需要num数组的原因了
a[++ cnt].l = read();
a[cnt] = ASK{-1, a[cnt].l, -1, num[a[cnt].l]};
a[++ cnt] = ASK{0, a[cnt-1].l, 1, read()};
b[++ cntb] = a[cnt].k;
num[a[cnt-1].l] = a[cnt].k;//*
}
}
sort(b + 1, b + cntb + 1);
int len = unique(b + 1, b + cntb + 1) - b - 1;
for(int i = 1; i <= cnt; ++ i) if(a[i].ty <= 0){
a[i].k = lower_bound(b + 1, b + len + 1, a[i].k) - b;
}
CDQ(1, len, 1, cnt);
for(int i = 1; i <= m; ++ i) if(ans[i]) printf("%d\n", b[ans[i]]);
return 0;
}