分类导航

程序笔记发布时间：2022-07-19 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了AcWing 255. 第K个数，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

原题链接

考察:主席树

思路:

利用二分的思想,即在主席树上二分,详细参考代码,主要记板子.

 1 #include <iostream>
 2 #include <cString>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 const int N = 100010;
 7 int n,m,root[n],idx,a[n];
 8 vector<int> v;
 9 struct Node{
10     int l,r,cnt;
11     Node operator=(const Node& X){
12          this->l = x.l;
13          this->r = x.r;
14          this->cnt = x.cnt;
15          return *this;    
16     }
17 }tr[N*21];
18 int find(int X)
19 {
20     return lower_bound(v.begin(),v.end(),X)-v.begin();
21 }
22 int build(int l,int r)
23 {
24     int p = ++idx;//构造主席树结点下标
25     if(l==r) return p;
26     int mid = l+r>>1;
27     tr[p].l = build(l,mid);//l代表左子树结点下标
28     tr[p].r = build(mid+1,r);//l,r不是区间范围
29     tr[p].cnt = 0;
30     return p;
31 }
32 int insert(int l,int r,int last,int val)
33 {
34     int p = ++idx;//建立新树,只需要上个版本的对应下标
35     tr[p] = tr[last];
36     if(l==r) {tr[p].cnt++;return p;}//返回新改变的点 
37     int mid = l+r>>1;
38     if(val<=mid) tr[p].l = insert(l,mid,tr[last].l,val);
39     else tr[p].r = insert(mid+1,r,tr[last].r,val);
40     tr[p].cnt = tr[tr[p].l].cnt+tr[tr[p].r].cnt;//更新 
41     return p;
42 }
43 int ask(int now,int last,int k,int l,int r)//询问[l,r]区间第k小
44 {//求[l,mid] 区间有x个数.if x<=k 在[l,mid]里找,否则[mid+1,r]找
45     if(l==r) return v[l];
46     int mid = l+r>>1;
47     int lcnt = tr[tr[now].l].cnt-tr[tr[last].l].cnt;//tr[l]代表[l,mid]区间
48     if(k<=lcnt) return ask(tr[now].l,tr[last].l,k,l,mid);
49     else return ask(tr[now].r,tr[last].r,k-lcnt,mid+1,r);
50 }
51 int main()
52 {
53     scanf("%d%d",&n,&@H_231_24@m);
54     for(int i=1;i<=n;i++)
55     {
56         scanf("%d",&a[i]);
57         v.push_BACk(a[i]); 
58     } 
59     sort(v.begin(),v.end());
60     v.erase(unique(v.begin(),v.end()),v.end());
61     root[0] = build(0,v.size()-1);
62     for(int i=1;i<=n;i++)
63         root[i] = insert(0,v.size()-1,root[i-1],find(a[i]));
64     while(m--)
65     {
66         int l,r,k;
67         scanf("%d%d%d",&l,&r,&k);
68         printf("%dn",ask(root[r],root[l-1],k,0,v.size()-1));
69     }
70     return 0;
71 }