静态区间第k大树套树解法-白红宇

静态区间第k大树套树解法

阅读量：4920 次

发布时间：2019-06-11

本文共 1400 字，大约阅读时间需要 4 分钟。

~~然而过不去你谷的模板~~

思路：

值域线段树\([l,r]\)代表一棵值域在\([l,r]\)范围内的点构成的一颗平衡树

平衡树的\(BST\)权值为点在序列中的位置

查询区间第\(k\)大值时

左区间在\([l,r]\)范围内的树的大小与\(k\)比较

大了进去，小了减掉换一边

关于建树

递归建估计是\(O(nlog^2n)\)的

Code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        const int N=1e5+10;int ch[N*20][2],val[N*20],siz[N*20],pos[N*20],root[N<<2],tot;#define ls ch[now][0]#define rs ch[now][1]int n,m,n_,a[N],b[N];void updata(int now){siz[now]=siz[ls]+siz[rs]+1;}void split(int now,int k,int &x,int &y){    if(!now) {x=y=0;return;}    if(pos[now]<=k)        x=now,split(rs,k,rs,y);    else        y=now,split(ls,k,x,ls);    updata(now);}int Merge(int x,int y){    if(!x||!y) return x+y;    if(val[x]

loc[N];void build(int id,int l,int r){ if(l==r) { for(int i=0;i

>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); for(int i=l;i<=r;i++) for(int j=0;j

>1,cnt; if((cnt=ask(id<<1,ql,qr))>=k) return query(id<<1,l,mid,ql,qr,k); else return query(id<<1|1,mid+1,r,ql,qr,k-cnt);}void init(){ scanf("%d%d",&n_,&m); for(int i=1;i<=n_;i++) scanf("%d",a+i),b[i]=a[i]; std::sort(a+1,a+1+n_); n=std::unique(a+1,a+1+n_)-a-1; for(int i=1;i<=n_;i++) loc[std::lower_bound(a+1,a+1+n,b[i])-a].push_back(i); build(1,1,n);}void work(){ for(int l,r,k,i=1;i<=m;i++) { scanf("%d%d%d",&l,&r,&k); printf("%d\n",query(1,1,n,l,r,k)); }}int main(){ init(),work(); return 0;}

2018.9.2

转载于:https://www.cnblogs.com/butterflydew/p/9575675.html

你可能感兴趣的文章