我们一般的线段树的节点下标是数组, 而我们只要把它变成值, 就能统计每个节点的数量了.
类似于桶的实现吧.
其实这个的线段树就是前缀和, 也可以用树状数组来代替.
至于查询 k 大, 只要二分就可以了.
数据范围大的时候通常先离散化数据, 所以算半个离线数据结构.
直接上代码
拿洛谷的平衡树模板 https://www.luogu.org/problemnew/show/P3369 为例.
这里由于懒得写线段树就拿树状数组代替了.
如果开心的话手动改成线段树就可以了.
- #include <bits/stdc++.h>
- using namespace std;
- const int N=1e6+1000;
- int read(){
- char c;int num,f=1;
- while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0';
- while(c=getchar(), isdigit(c))num=num*10+c-'0';
- return f*num;
- }
- int order[N],act[N][2],cnt,t[N],n;
- bool cmp(int a,int b){return a<b;}
- int fd(int a){
- int l=1,r=cnt,mid;
- while(l<=r){
- mid=(l+r)>>1;
- if(order[mid]==a)return mid;
- else if(order[mid]>a)r=mid-1;
- else l=mid+1;
- }
- return -1;
- }
- void add(int x,int val){for(;x<=cnt;x+=x&-x)t[x]+=val;}
- int query(int x){
- int ans=0;
- for(;x;x-=x&-x)ans+=t[x];
- return ans;
- }
- void Insert(int x){add(x,1);}
- void Del(int x){if(query(x)-query(x-1))add(x,-1);}
- int Getrank(int x){return query(x-1)+1;}
- int Getnum(int rk){
- int l=0,r=cnt,mid,a,b;
- while(l<=r){
- mid=(l+r)>>1;
- a=query(mid-1);
- b=query(mid);
- if(b>=rk&&a<rk)return order[mid];
- if(b<rk)l=mid+1;
- else r=mid-1;
- }
- return -1;
- }
- int Getpre(int x){return Getnum(Getrank(x)-1);}
- int Getnxt(int x){return Getnum(query(x)+1);}
- int main()
- {
- n=read();
- for(int i=1;i<=n;i++){
- act[i][0]=read();
- act[i][1]=read();
- order[++cnt]=act[i][1];
- }
- sort(order+1,order+1+cnt,cmp);
- cnt=unique(order+1,order+1+cnt)-order;
- for(int i=1;i<=n;i++){
- int opt=act[i][0],x=fd(act[i][1]);
- if(opt==1)Insert(x);
- if(opt==2)Del(x);
- if(opt==3)printf("%d\n",Getrank(x));
- if(opt==4)printf("%d\n",Getnum(act[i][1]));
- if(opt==5)printf("%d\n",Getpre(x));
- if(opt==6)printf("%d\n",Getnxt(x));
- }
- return 0;
- }
- View Code
权值线段树
来源: http://www.bubuko.com/infodetail-2853623.html