权值线段树

其实权值线段树在学习主席树的时候我就提到过这个东西。

权值线段树和普通线段树之间区别就是在于 它存储的是 区间内数的个数

 

所以用这种数据结构我们可以求解一个 完整区间的第k大 ，要注意和主席树的区别。 主席树更加强大！！

 

学了主席树反过来学权值线段树超简单

 

直接上例题：黑匣子https://www.luogu.org/problemnew/show/P1801  

 

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <vector>
 6 #include <map>
 7 #include <random>
 8 #include <sqlite3.h>
 9 
10 const int maxn = 3e5 + 10;
11 
12 int k;
13 int arr[maxn];
14 int u[maxn];
15 
16 struct val_segment_tree{
17     int l,r;
18     int val;
19 }tree[maxn<<2];
20 
21 void build(int nod,int l,int r) {
22     tree[nod].l = l;
23     tree[nod].r = r;
24     if (l == r)
25         return ;
26     int mid = (l + r) >> 1;
27     build(nod<<1,l,mid);
28     build((nod<<1)+1,mid+1,r);
29 }
30 
31 void update(int nod,int t) {
32     int l =tree[nod].l,r = tree[nod].r;
33     if (l == r) {
34         tree[nod].val++;
35         return ;
36     }
37     int mid = (l + r) >> 1;
38     if (t <= mid) {
39         update(nod<<1,t);
40     }
41     else
42         update((nod<<1)+1,t);
43     tree[nod].val = tree[nod<<1].val + tree[(nod<<1)+1].val;
44 }
45 //查找整个区间第k大
46 int query(int nod,int t) {
47     int l = tree[nod].l,r = tree[nod].r;
48     if (l == r)
49         return tree[nod].l;
50     if (t <= tree[nod<<1].val)
51         return query(nod<<1,t);
52     else
53         return query((nod<<1)+1,t-tree[nod<<1].val);
54 }
55 
56 std::vector<int> v;
57 int getid(int x) {
58     return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
59 }
60 
61 
62 int main() {
63     int n,m;
64     scanf("%d%d",&m,&n);
65     for (int i=1;i<=m;i++) {
66         scanf("%d",&arr[i]);
67         v.push_back(arr[i]);
68     }
69     for (int i=1;i<=n;i++) {
70         scanf("%d",&u[i]);
71     }
72     std::sort(v.begin(),v.end());
73     v.erase(std::unique(v.begin(),v.end()),v.end());
74     int len = v.size();
75     build(1,1,len);
76     int h = 0;
77     while (n != h ) {
78         h++;
79         for (int i=u[h-1]+1;i<=u[h];i++) {
80             int val = getid(arr[i]);
81             update(1,val);
82         }
83         printf("%d\n",v[query(1,++k)-1]);
84     }
85 
86 }