盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

ZOJ2112 Dynamic Rankings(动态区间第K大 树状数组套主席树)

题目

源地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112

题意

动态查询区间第K大数,带修改

思路

http://www.cnblogs.com/Empress/p/4659824.html
需要将询问离线处理,将一开始的数列用主席树维护。之后修改的部分用N个树状数组来维护,每次更新logn棵树。
时间复杂度:nlog^2n

代码

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int N = 60000 + 10;
#define lson l, m
#define rson m + 1, r
int a[N], Hash[N];
int root[N], ln[N << 5], rn[N << 5], sum[N << 5];
int S[N];
int n, m, tot;
struct node {
int l, r, k;
bool Q;
}op[10005];
int build(int l, int r) {
int rt = ++tot;
sum[rt] = 0;
if (l != r) {
int m = l + r >> 1;
ln[rt] = build(lson);
rn[rt] = build(rson);
}
return rt;
}
int update(int pre, int l, int r, int x, int val) {
int rt = ++tot;
ln[rt] = ln[pre], rn[rt] = rn[pre], sum[rt] = sum[pre] + val;
if (l < r) {
int m = l + r >> 1;
if (x <= m) ln[rt] = update(ln[pre], lson, x, val);
else rn[rt] = update(rn[pre], rson, x, val);
}
return rt;
}
int lowbit(int x) {
return x & -x;
}
int use[N];
void add(int x, int pos, int val) {
while(x <= n) {
S[x] = update(S[x], 1, m, pos, val);
x += lowbit(x);
}
}
int get_sum(int x) {
int ret = 0;
while(x) {
ret += sum[ln[use[x]]];
x -= lowbit(x);
}
return ret;
}
int query(int u, int v, int lr, int rr, int l, int r, int k) {
if (l >= r) return l;
int m = l + r >> 1;
int tmp = get_sum(v) - get_sum(u) + sum[ln[rr]] - sum[ln[lr]];
if (tmp >= k) {
for (int i = u; i; i -= lowbit(i)) use[i] = ln[use[i]];
for (int i = v; i; i -= lowbit(i)) use[i] = ln[use[i]];
return query(u, v, ln[lr], ln[rr], lson, k);
} else {
for (int i = u; i; i -= lowbit(i)) use[i] = rn[use[i]];
for (int i = v; i; i -= lowbit(i)) use[i] = rn[use[i]];
return query(u, v, rn[lr], rn[rr], rson, k - tmp);
}
}
void modify(int x, int p, int d) {
while(x <= n) {
S[x] = update(S[x], 1, m, p, d);
x += lowbit(x);
}
}
int main () {
int t, q;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &q);
m = tot = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
Hash[++m] = a[i];
}
char s[10];
for (int i = 0; i < q; i++) {
scanf("%s", s);
if (s[0] == 'Q') {
scanf("%d%d%d", &op[i].l, &op[i].r, &op[i].k);
op[i].Q = 1;
} else {
scanf("%d%d", &op[i].l, &op[i].r);
op[i].Q = 0;
Hash[++m] = op[i].r;
}
}
sort(Hash + 1, Hash + m + 1);
m = unique(Hash + 1, Hash + m + 1) - Hash - 1;
root[0] = build(1, m);
for (int i = 1; i <= n; i++) root[i] = update(root[i - 1], 1, m, lower_bound(Hash + 1, Hash + m + 1, a[i]) - Hash, 1);
for (int i = 1; i <= n; i++) S[i] = root[0];
for (int i = 0; i < q; i++) {
if (op[i].Q) {
for (int j = op[i].l - 1; j; j -= lowbit(j)) use[j] = S[j];
for (int j = op[i].r; j; j -= lowbit(j)) use[j] = S[j];
printf("%d\n", Hash[query(op[i].l - 1, op[i].r, root[op[i].l - 1], root[op[i].r], 1, m, op[i].k)]);
} else {
modify(op[i].l, lower_bound(Hash + 1, Hash + m + 1, a[op[i].l]) - Hash, -1);
modify(op[i].l, lower_bound(Hash + 1, Hash + m + 1, op[i].r) - Hash, 1);
a[op[i].l] = op[i].r;
}
}
}
return 0;
}