线段树求解区间第k大

具体哪道题目就不说了，区间第k大可以说是很常见的题目。写了一上午线段树终于是记起了一点以前学过的东西。

这里说的是没有修改的区间查询。对于线段树的结构体，一开始搜了一下，说是要按照归并排序的方法去建树，所以说每个节点要记录数组咯？？这样的话每个节点还要记一个数组，太麻烦，空间占用也变大了。所以有另一种方法，直接用一个数组，在节点中记录该节点对应的该数组中的范围，这样就可以节省空间。

建好树之后就是查询，这里要到两个查询，第一个是查询给定值在给定范围内的下标，第二个查询是第一个查询中要调用的，用来寻找在具体的某一个节点中它的下标。最后在主程序中二分答案，找到其在给定范围的下标，判断即可。

#include<stdio.h>
#include<string.h>
#define maxn 10100
#define inf 1111111111
struct s{
    int l,r,ll,rr;
};
s tr[maxn*4];
int d[maxn*20],cnt;
int a[maxn];
void build(int rt,int lr,int rr){
    tr[rt].l=lr;
    tr[rt].r=rr;
    if(lr==rr){
        d[++cnt]=a[lr];
        tr[rt].ll=cnt;
        tr[rt].rr=cnt;
     //   printf("%d   \n",d[lr]);
        return ;
    }
    int mid=(tr[rt].l+tr[rt].r)>>1;
    build(rt*2,lr,mid);
    build(rt*2+1,mid+1,rr);
    tr[rt].ll=cnt+1;
  //  printf("cnt==%d\n",cnt);
    int l1=tr[rt*2].ll,r1=tr[rt*2].rr;
    int l2=tr[rt*2+1].ll,r2=tr[rt*2+1].rr;
    while(l1<=r1&&l2<=r2){
        if(d[l1]<d[l2]){
            d[++cnt]=d[l1];
            l1++;
        }
        else{
            d[++cnt]=d[l2];
            l2++;
        }
      //  printf("sdfas\n");
    }
    while(l1<=r1){
        d[++cnt]=d[l1];
        l1++;
    }
    while(l2<=r2){
        d[++cnt]=d[l2];
        l2++;
    }
    rt[tr].rr=cnt;
}
int query2(int ls,int rs,int ans){
    if(ans>=d[rs]) return rs-ls+1;
    if(ans<d[ls]) return 0;
    int mid;
    int ll=ls,rr=rs;
    while(ls<rs){

        mid=(ls+rs)>>1;

        if(ans>=d[mid]) ls=mid+1;
        else rs=mid;
    }
    return ls-ll;
}
int query1(int rt,int ls,int rs,int ans){
    if(ls<=tr[rt].l&&rs>=tr[rt].r){
          //  printf("ll===%d   rr====%d\n",tr[rt].ll,tr[rt].rr);
        return query2(tr[rt].ll,tr[rt].rr,ans);
    }
    int mid=(tr[rt].l+tr[rt].r)>>1;
    int hh=0;
    if(ls<=mid) hh+=query1(rt*2,ls,rs,ans);
    if(rs>=mid+1) hh+=query1(rt*2+1,ls,rs,ans);
    return hh;
}
int main(){
    int n,x,y,k;
    cnt=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    int m;
    scanf("%d",&m);
    while(m--){
        scanf("%d%d%d",&x,&y,&k);
        k=y-x-k+2;
      //  printf("k==%d\n",k);
        int lll=-inf,rrr=inf,mid;
        while(lll<rrr){
            mid=(lll+rrr)>>1;
            int tmp=query1(1,x,y,mid);
        //    printf("lll===%d  rrr====%d   mid==%d tmp==%d\n",lll,rrr,mid,tmp);
            if(tmp<k)
                lll=mid+1;
            else rrr=mid;
        }
        printf("%d\n",lll);
    }
   // for(int i=1;i<=cnt;i++)printf("%d ",d[i]);
    return 0;
}

所以说我以前到底线段树学了些什么，，，

加油，马上蓝桥杯。