1. 题目

传送门=￣ω￣=

大意：给你一个数组和一堆询问，询问有三个参数 l,r,k，要你输出数组区间 [l,r] 中排名第 k 的数字是多少

出题人你个傻逼又不说数据组数范围不然分块也能过结果你卡得我线段树不打读入优化都不一定能过，还必须打 inline信不信我切了你的小鸡鸡╭(╯^╰)╮

2. 题解

首先简单讲下分块的写法吧

先分块，再对每个块排序，最后二分答案，对于每个枚举出的答案，在块内二分、块外暴力，算出它的排名，最后就可以确定答案了。

代码长这样（Warning: 会 TLE!）：

#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;
inline int read()
{
    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;
}

上面那个理论上没错，只是会 TLE

所以我们必须打线段树。

线段树嘛，维护区间。每个节点都会对应着一个区间，那我们就让每个节点里有一个数组，这个数组就是它对应的区间排序后的样子。然后我们二分答案以后检测答案是否合法，就直接找到区间对应的节点们，在节点的数组里二分找到当前答案在这个区间里排第几，最后加在一起就是它的排名了。

区间排序就在建树时用归并排序搞掉了。

至于每个节点要对应一个数组，直接用 int 的话空间太大，$N^2$的空间复杂度，无法接受。而开 vector 又太慢了。所以就搞个 “公共储存池”（其实是我瞎 YY 出的名字，就是个公共数组而已），每个节点记录在这个公共数组里它所占用的数组左端点编号，数组右端点编号。这样空间复杂度是 $NlogN$的。

这样每次查询是 $log^3 N$的。最后复杂度就是 $Mlog^3 N$的，总共复杂度就是 $TMlog^3 N$的。

代码：

#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));
    return tot;
} 
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;
}