Kth number———主席树模板

传送门HDU2665

描述

Give you a sequence and ask you the kth big number of a inteval.

输入

The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]

输出

For each test case, output m lines. Each line contains the kth big number.

样例

  • Input
    1
    10 1
    1 4 2 3 5 6 7 8 9 0
    1 3 2
  • Output
    2

题解

  • 题意:n个数q次询问,每次给一个区间[l,r]和一个数k,求区间中第k大的数。(其实是第k小来着,不知道是出题人的锅还是阅读理解有问题…)
  • 权值线段树:节点num[i]维护i出现次数的线段树,主席树就是可持续化权值线段树,用于求区间第k小的数。
  • 在建树时,每插入一个数就新建一颗线段树,用i时刻表示a[i]插入线段树的时刻,节点维护数组中每个元素在每个时刻出现的次数,用root[i]则表示i时刻所建的线段树的顶点。通过线段树的性质不难发现,插入一个数时只会经过log(n)个点,我们只需要新建这log(n)个点即可,其他的可以直接使用上时刻状态的节点。
  • 要查询区间a[2]~a[5]时,我们首先把第1颗树和第5颗树拿出来,把树种对应位置的节点相减,就可以得到a[2]~a[5]内节点所包含范围内的数的个数(前缀和思想)。如两个代表区间[1,4]的节点相减等于2,就说明在a[2]~a[5]内有2个数在1到4之间。
  • 对于一个区间[l,r],我们每次算出在[l,mid]范围内的数x,如果x>=k,说明第k大的数在左边,如果x < k,说明第k大在右边,就在右边找第k-x大的数(因为左边已经有x个数了)
  • 为了节省空间,将数组元素离散化,每次插入这个数在数组排序并去重后的位次。
  • 若排序去重后数组长度为m的话,那么线段树的空间需要mlg(m),每次查询的时间复杂度为lg(m),建树的时间复杂度为nlg(m);
  • 很好的一篇博客

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
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define INIT(a,b) memset(a,b,sizeof(a))
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define S(d) scanf("%d",&d)
#define SLL(d) scanf("%lld",&d)
#define P(d) printf("%d\n",d)
#define PLL(d) printf("%lld\n",d)
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e5+7;
const int M=2e6+7;
const int mod=1e9+7;
int a[N],b[N],L[N*20],R[N*20],num[N*20],root[N];
int tot=0;
int build(int l,int r){
int now=++tot;
if(l<r){
int mid=l+r>>1;
L[now]=build(l,mid);
R[now]=build(mid+1,r);
}
return now;
}
int update(int pre,int l,int r,int x){
int now=++tot;
L[now]=L[pre],R[now]=R[pre],num[now]=num[pre]+1;//先将左右节点都连在上一棵树上
int mid=l+r>>1;
if(l<r){
//新建左节点或新建右节点
if(x<=mid) L[now]=update(L[pre],l,mid,x);
else R[now]=update(R[pre],mid+1,r,x);
}
return now;
}
int query(int u,int v,int l,int r,int k){
//左边数的个数x>=k,说明第k位在左边,否则在右边找第k-x位
if(l==r) return l;
int x=num[L[v]]-num[L[u]];
int mid=l+r>>1;
if(x>=k) return query(L[u],L[v],l,mid,k);
else return query(R[u],R[v],mid+1,r,k-x);
}
int main(){
int ca;S(ca);
int n,q,s,t,k,tem;
while(ca--){
tot=0;
S(n),S(q);
rep(i,1,n) {
S(a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
int m=unique(b+1,b+1+n)-b-1;//去重
root[0]=build(1,m);//建空树
rep(i,1,n){
tem=lower_bound(b+1,b+m+1,a[i])-b;
root[i]=update(root[i-1],1,m,tem);
//离散化,用位次表示数字并插入主席树
}
while(q--){
S(s),S(t),S(k);
tem=query(root[s-1],root[t],1,m,k);
P(b[tem]);
}
}
return 0;
}
Donate comment here