「POJ-2104」K-th Number-主席树

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$.
题意:就是求区间第 $k$ 大。

链接

poj2104

题解

裸的主席树模板题,注意 poj 评测机较慢,不停地 $new$ 会TLE,要静态开内存。

代码

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
#include <cstdio>
#include <climits>
#include <algorithm>
#include <new>
#include <cctype>
#include <cstring>
#include <iostream>
inline char read() {
static const int IO_LEN = 1024 * 1024;
static char buf[IO_LEN], *ioh, *iot;
if (ioh == iot) {
iot = (ioh = buf) + fread(buf, 1, IO_LEN, stdin);
if (ioh == iot) return -1;
}
return *ioh++;
}
template<class T>
inline void read(T &x) {
static bool iosig = 0;
static char ioc;
for (iosig = 0, ioc = read(); !isdigit(ioc); ioc = read()) if (ioc == '-') iosig = 1;
for (x = 0; isdigit(ioc); ioc = read()) x = (x << 1) + (x << 3) + (ioc ^ '0');
if (iosig) x = -x;
}
template<class T, size_t size>
struct MemoryPool {
T buf[size], *tail, *st[size];
int top;
MemoryPool() : top(0), tail(buf) {}
inline T *alloc() { return top ? st[--top] : tail++; }
inline void recycle(T *x) { st[top++] = x;}
};
const int MAXN = 3000000;
struct ChairmanTree {
struct Node {
int l, r;
Node *lc, *rc;
int cnt;
static inline Node *newNode(MemoryPool<Node, MAXN> &pool, const int l, const int r, Node *lc = NULL, Node *rc = NULL) {
Node *tmp = pool.alloc();
tmp->l = l, tmp->r = r, tmp->lc = lc, tmp->rc = rc, tmp->cnt = (lc ? lc->cnt : 0) + (rc ? rc->cnt : 0);
return tmp;
}
static inline Node *newNode(MemoryPool<Node, MAXN> &pool, const int l, const int r, const int cnt) {
Node *tmp = pool.alloc();
tmp->l = l, tmp->r = r, tmp->cnt = cnt, tmp->lc = NULL, tmp->rc = NULL;
return tmp;
}
inline void pushDown(MemoryPool<Node, MAXN> &pool) {
if (lc && rc) return;
register int mid = l + r >> 1;
if (!lc) lc = newNode(pool, l, mid);
if (!rc) rc = newNode(pool, mid + 1, r);
}
inline Node *insert(MemoryPool<Node, MAXN> &pool, const int num) {
if (num < l || num > r) return this;
else if (num == l && num == r) return newNode(pool, l, r, this->cnt + 1);
else {
register int mid = l + r >> 1;
pushDown(pool);
if (num <= mid) return newNode(pool, l, r, lc->insert(pool, num), rc);
else return newNode(pool, l, r, lc, rc->insert(pool, num));
}
}
inline int rank() const { return lc ? lc->cnt : 0; }
} *root[MAXN + 1];
MemoryPool<Node, MAXN> pool;
int n;
inline void build(const int *a, const int n) {
this->n = n;
root[0] = Node::newNode(pool, 0, n - 1);
for (register int i = 1; i <= n; i++)
root[i] = root[i - 1]->insert(pool, a[i - 1]);
}
inline int query(const int l, const int r, int k) {
Node *L = root[l - 1], *R = root[r];
register int min = 0, max = n - 1;
while (min != max) {
L->pushDown(pool), R->pushDown(pool);
register int mid = min + max >> 1, t = R->rank() - L->rank();
if (k <= t) L = L->lc, R = R->lc, max = mid;
else k -= t, L = L->rc, R = R->rc, min = mid + 1;
}
return min;
}
} t;
int n, m, a[MAXN];
int main() {
read(n), read(m);
for (register int i = 0; i < n; i++) read(a[i]);
static int set[MAXN];
memcpy(set, a, sizeof(a));
std::sort(set, set + n);
int *end = std::unique(set, set + n);
for (register int i = 0; i < n; i++) a[i] = std::lower_bound(set, end, a[i]) - set;
t.build(a, n);
for (register int i = 0, l, r, k; i < m; i++) {
read(l), read(r), read(k);
register int ans = t.query(l, r, k);
std::cout << set[ans] << "\n";
}
return 0;
}
分享到