# 2. 题解

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>void IN(_Tp&dig)
{
char c=getchar();dig=0;int f=1;
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
dig*=f;
}
int t,n,q,sqn,arr[101000],d[101000],bi[101000],minl,maxl;
{
bool minus=0;int dig=0;char c=getchar();
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')minus=1,c=getchar();
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
return minus?-dig:dig;
}
inline int getpos(int l,int r,int k)
{
int pos=0,lim=min(bi[l]*sqn,r);
for(int i=l;i<=lim;i++)if(arr[i]<k)++pos;
if(bi[l]!=bi[r])for(int i=(bi[r]-1)*sqn+1;i<=r;i++)if(arr[i]<k)++pos;
for(int i=bi[l]+1;i<bi[r];i++)
pos+=(int)(lower_bound(d+(i-1)*sqn+1,d+i*sqn+1,k)-(d+(i-1)*sqn+1));
return pos;
}
inline void getans(int l,int r,int k)
{
int a=minl,b=maxl,m;
while(a!=b)
{
m=(a+b)>>1;
if(getpos(l,r,m)<k)a=m+1;else b=m;
}
printf("%d\n",a-1);
}
int main()
{
IN(t);
while(minl=INT_MAX,maxl=INT_MIN,t-->0)
{
IN(n),IN(q),sqn=sqrt(n);
for(int i=1;i<=n;i++)
IN(arr[i]),d[i]=arr[i],
maxl=max(maxl,arr[i]),minl=min(minl,arr[i]),bi[i]=(i-1)/sqn+1;
minl--,maxl++;
for(int i=1;i<=bi[n];i++)sort(d+1+(i-1)*sqn,d+1+min(n,i*sqn));
for(int i=1,l,r,k;i<=q;i++)IN(l),IN(r),IN(k),getans(l,r,k);
}
return 0;
}


#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c=getchar();dig=0;int f=1;
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
dig*=f;
}
struct N{int l,r,a,b;}e[400005];
int t,n,m,lim1,lim2,d[2000005],dtop;
inline void build(int l,int r,int a)
{
e[a].l=l,e[a].r=r,e[a].a=dtop,e[a].b=dtop+r-l,dtop+=r-l+1;
if(l==r)
{
IN(d[e[a].a]),lim1=min(lim1,d[e[a].a]),lim2=max(lim2,d[e[a].a]);
return;
}
build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a));
int i=e[LS(a)].a,j=e[RS(a)].a,k=e[a].a;
while(i<=e[LS(a)].b||j<=e[RS(a)].b)
{
if(i>e[LS(a)].b)d[k++]=d[j++];
else if(j>e[RS(a)].b)d[k++]=d[i++];
else if(d[i]<d[j])d[k++]=d[i++];
else d[k++]=d[j++];
}
}
inline int query(int l,int r,int k,int a)
{
if(l<=e[a].l&&e[a].r<=r)
return (int)(lower_bound(d+e[a].a,d+e[a].b+1,k)-(d+e[a].a));
int tot=0;
if(l<=((e[a].l+e[a].r)>>1))tot+=query(l,r,k,LS(a));
if(r>((e[a].l+e[a].r)>>1))tot+=query(l,r,k,RS(a));
}
inline int work(int a,int b,int k)
{
int l=lim1,r=lim2,m;
while(l!=r)
{
m=(l+r+1)>>1;
int tmp=query(a,b,m,1);
if(tmp<k)l=m;else r=m-1;
}
return l;
}
int main()
{
IN(t);
while(lim1=INT_MAX,lim2=INT_MIN,dtop=0,t--)
{
IN(n),IN(m),build(1,n,1);
for(int i=1,a,b,k;i<=m;i++)IN(a),IN(b),IN(k),printf("%d\n",work(a,b,k));
}
return 0;
}


### 6 条评论

哦，打错了。
谢谢 dalao～

#### konnyakuxzy · 2018年2月5日 9:43 下午

QvQ 突然发现这条回复
重新补充一下啊，经过仔细研究，，，这里这个算法复杂度是 $O(TMlog_2^3N)$的

#### boshi · 2017年7月2日 2:25 下午

inline+register=-1s

#### 【题解】 Dynamic Rankings 动态区间第k小问题 二分答案+树套树（线段树套splay） BZOJ – 1901 | K-XZY · 2018年1月4日 3:59 下午

[…] 二分答案套线段树：传送门=￣ω￣= […]

#### 【题解】 K-th Number 主席树 POJ – 2104 | K-XZY · 2018年1月4日 1:29 下午

[…] 以前写过一个二分套线段树的题解：传送门=￣ω￣=（题目一样，就是那个有多组数据这个没有）[…]