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;
}
05-08 15:23