这个东西有很多名字,主席树,可持久化线段树,函数式线段树。
我们用前缀和的思想,对每个前缀建线段树,区间表示数的大小,进行二分。
我在B站学算法:https://www.bilibili.com/video/av4619406/?from=search&seid=2734527038623001186#page=2
这个人讲的很不错,十分钟学代码超赚啊。
1 #include<bits.stdc++.h>
2 using namespace std;
3 const int N=1e5+10;
4 vector<int>v;
5 struct node
6 {
7 int l,r,s;
8 }t[N*40];
9 int rt[N],a[N],cnt;
10 int get(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
11 void update(int l,int r,int x,int &y,int pos)
12 {
13 y=++cnt;t[y]=t[x];t[y].s++;
14 if(l==r)return;
15 int m=(l+r)>>1;
16 if(pos<=m)update(l,m,t[x].l,t[y].l,pos);
17 else update(m+1,r,t[x].r,t[y].r,pos);
18 }
19 int query(int l,int r,int x,int y,int num)
20 {
21 if(l==r)return l;
22 int sum=t[t[y].l].s-t[t[x].l].s;
23 int m=(l+r)>>1;
24 if(sum>=num)return query(l,m,t[x].l,t[y].l,num);
25 else return query(m+1,r,t[x].r,t[y].r,num-sum);
26 }
27 int main()
28 {
29 int n,m;int x,l,r;
30 scanf("%d%d",&n,&m);
31 for(int i=1;i<=n;++i)scanf("%d",&a[i]),v.push_back(a[i]);
32 sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
33 for(int i=1;i<=n;++i)update(1,n,rt[i-1],rt[i],get(a[i]));
34 for(int i=1;i<=m;++i)
35 {
36 scanf("%d%d%d",&l,&r,&x);
37 printf("%d\n",v[query(1,n,rt[l-1],rt[r],x)-1]);
38 }
39 return 0;
40 }
原文链接: https://www.cnblogs.com/nbwzyzngyl/p/7978392.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/264692
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!