cogs930找第k小的数(k-th number)

---

原题链接

---

题解

好题。。。

终极版是bzoj3065（然而并不会）

先讲这个题。。。

维护\(n+1\)个值域线段树（用主席树），标号\(0\) ~ \(n\)，第\(i\)个表示前i个的。然后区间\([l,r]\)就可以通过第\(r\)个线段树减去第\(l-1\)个线段树来得到。这里就在查询操作里把一个根改成两个，边查询边减法。。。

考虑最终减完以后的线段树（并不需要生成这个），树根>=k，就查询\(ls\)，否则查询\(rs\)。然后直到叶子节点输出就可以辣！



当然要加个离散化。

---

Code

// It is made by XZZ

#include<cstdio>

#include<algorithm>

#define Fname "kth"

using namespace std;

#define rep(a,b,c) for(rg int a=b;a<=c;a++)

#define drep(a,b,c) for(rg int a=b;a>=c;a--)

#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])

#define il inline

#define rg register

#define vd void

#define mid ((l+r)>>1)

typedef long long ll;

il int gi(){

    rg int x=0;rg char ch=getchar();

    while(ch<'0'||ch>'9')ch=getchar();

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x;

}

const int maxn=100010;

int n,m;

typedef struct node* point;

point null;

struct node{

    int data;point ls,rs;

    node(point _ls=null,point _rs=null,int _data=0){ls=_ls,rs=_rs,data=_data;}

};

point root[maxn];

int num[maxn],data[maxn];

il point build(int l,int r){

    if(l==r)return new node;

    return new node(build(l,mid),build(mid+1,r));

}

il vd copy(point&a,point b){

    if(b==null)a=null;

    else a=new node(b->ls,b->rs,b->data);

}

il vd Update(point&s,point now,int l,int r,int&pos){

    copy(s,now);++s->data;

    if(l==r)return;

    if(mid<pos)Update(s->rs,now->rs,mid+1,r,pos);

    else Update(s->ls,now->ls,l,mid,pos);

}

il int Query(int a,int b,int l,int r,int k){

    point x=root[a],y=root[b];

    while(l<r)

	if(x->ls->data-y->ls->data>=k)x=x->ls,y=y->ls,r=mid;

	else k-=x->ls->data-y->ls->data,x=x->rs,y=y->rs,l=mid+1;

    return r;

}

int main(){

    n=gi(),m=gi();

    rep(i,1,n)num[i]=data[i]=gi();

    sort(data+1,data+n+1);

    int tot=unique(data+1,data+n+1)-data-1;

    rep(i,1,n)num[i]=lower_bound(data+1,data+tot+1,num[i])-data;

    null=new node;

    null->ls=null->rs=null;

    root[0]=build(1,tot);

    rep(i,1,n)Update(root[i],root[i-1],1,tot,num[i]);

    int l,r,k;

    while(m--)l=gi(),r=gi(),k=gi(),printf("%d\n",data[Query(r,l-1,1,tot,k)]);

    return 0;

}