模板 静态区间第K小(主席树)

传送门
啊,推了一晚上,大概搞定了吧。


题目大意

给定一个序列$a_{k\in [1,n]}$,$q$次询问,每次询问$[l,r]$中第$K$小的数。

解析

主席树

定义

有人说这就是可持久化线段树,没怎么懂这种说法。
主席树其实就是一堆权值线段树,第$i$棵表示的是序列$a_{k\in [1,i]}$的权值线段树。
那这样不会超空间吗?
其实不会,因为第$i$棵和第$i+1$棵权值线段树之间可能有很多公共结点。
比如说${3,1,2,4,5}$这个主席树,建出来是这样的。

发现从第$i-1$棵加到第$i$棵时,只要管新加入的数$val$是应该划分到$[l,mid]$还是$[mid+1,r]$这个区间就好了。
如果$val\in [l,mid]$,那么当前结点的右儿子就和前一棵的右儿子完全相同,这时候递归处理它们的左儿子就行了。
反之,如果$val\in [mid+1,r]$,那么左儿子完全相同,递归右儿子就可以了。
这样就可以共用结点了,那么动态开点就可以了。

性质

由于保存的是区间的权值线段树,主席树上的数值具有区间可加性!
这是一个非常好的性质,用两棵权值线段树的$query$值相减就可以方便我们在$O(log_2n)$的时间内查询一个$cnt=\sum_{i\in [l,r]} [a_i \le val]$,方便查询一个数在区间内的排名(可能还要稍微修改一下,问题不大)。
这就差不多了。
时间复杂度应该是$O(n\ log_2n)$的,空间复杂度动态开点。

Code

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
#define DREP(i, s, e) for(int i = s; i >= e ;i--)
#define REP(i, s, e) for(int i = s; i <= e ;i++)

#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b)
#define chkmin(a, b) a = min(a, b)

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 10;

template <typename T> inline T read()
{
T ans(0), p(1);
char c = getchar();
while (!isdigit(c))
{
if (c == '-') p = -1;
c = getchar();
}
while (isdigit(c))
{
ans = ans * 10 + c - 48;
c = getchar();
}
return ans * p;
}

int a[maxn], b[maxn], n, m, q;

#define mid (l + r >> 1)
#define lson p -> ls, l, mid
#define rson p -> rs, mid + 1, r

struct node *null;

struct node
{
node *ls, *rs;int sum;
node() : ls(null), rs(null), sum(0){}
}*rt[maxn];

void build(node *pre, node *&p, int l, int r, int val)
{
p = new node();
p -> ls = pre -> ls;
p -> rs = pre -> rs;
p -> sum = pre -> sum + 1;
if (l >= r) return;
else if (val <= mid)
build(pre -> ls, lson, val);
else
build(pre -> rs, rson, val);
}


int query(node *u, node *v, int l, int r, int k)
{
if (l >= r) return l;
int x = v -> ls -> sum - u -> ls -> sum;
if (x < k) return query(u -> rs, v -> rs, mid + 1, r, k - x);
else return query(u -> ls, v -> ls, l, mid, k);
}

int main()
{
#ifdef CraZYali
freopen("3834-new-new.in", "r", stdin);
freopen("3834-new-new.out", "w", stdout);
#endif
cin >> n >> q;
REP(i, 1, n) b[i] = a[i] = read<int>();
sort(b + 1, b + 1 + n);
m = unique(b + 1, b + 1 + n) - b - 1;
rt[0] = null = new node();
null -> ls = null;null -> rs = null;null -> sum = 0;
REP(i, 1, n)
{
rt[i] = null;
build(rt[i-1], rt[i], 1, m, lower_bound(b + 1, b + 1 + m, a[i]) - b);
}
while (q --> 0)
{
int L = read<int>(), R = read<int>(), k = read<int>();
printf("%d\n", b[query(rt[L-1], rt[R], 1, m, k)]);
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×