用主席树吊打CDQ
其实这道题是整体二分，像CDQ而已。
考虑一个询问$l_i,r_i$，只有前$i-1$个修改(把赋值当成修改)对其可能产生贡献。
那么第一维是时间，第二维是值域，第三维是位置。
第二维的意思也就是数的值，第三维是数的位置。
如果当前修改的值在值域$[l,r]$上小于等于$mid$，就意味着这个修改，会对询问产生贡献，因此在相应位置上$+1$，并将其推入值域$[l,mid]$上，继续对左半区询问产生贡献。反之则由于其大于$mid$，对于询问不会产生贡献，因此推入右区间。
那么这道题也就解决了。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=11e4+10;
const int inf=1e9+5;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int op,x,y,z;}q[N],lq[N],rq[N];
int ans[5050],c[N],n;
inline void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
inline int ask(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
void solve(int l,int r,int st,int ed)
{
    int mid=l+r>>1;
    if(l==r){for(int i=st;i<=ed;i++)ans[q[i].op]=l;return ;}
    int ls=0,rs=0;
    for(int i=st;i<=ed;i++)
    {
        if(!q[i].op)
        {
            if(q[i].y<=mid)add(q[i].x,1),lq[++ls]=q[i];
            else rq[++rs]=q[i];
        }
        else
        {
            int cnt=ask(q[i].y)-ask(q[i].x-1);//统计[l,r]区间‘1’的数量
            if(cnt>=q[i].z)lq[++ls]=q[i];
            else q[i].z-=cnt,rq[++rs]=q[i];//[q[i].x,q[i].y]有cnt个数小于mid ，减去cnt，再进入[mid+1,r]值域 ，说明这个询问的区间第k小的值大于mid
        }
    }
    for(int i=1;i<=ls;i++)if(!lq[i].op)add(lq[i].x,-1);
    for(int i=1;i<=ls;i++)q[st+i-1]=lq[i];
    for(int i=1;i<=rs;i++)q[st+i+ls-1]=rq[i];//按值域排 
    if(ls)solve(l,mid,st,st+ls-1);
    if(rs)solve(mid+1,r,st+ls,ed);
}
int main()
{
    qr(n);int m;qr(m);
    for(int i=1;i<=n;i++)q[i].op=0,q[i].x=i,qr(q[i].y);
    for(int i=n+1;i<=n+m;i++)q[i].op=i-n,qr(q[i].x),qr(q[i].y),qr(q[i].z);
    solve(-inf,inf,1,n+m);
    for(int i=1;i<=m;i++)qw(ans[i]),puts("");
    return 0;
}

附上一个主席树做法：

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=1e5+10;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int a[N],arr[N],n,len;
void disc()
{
    sort(arr+1,arr+n+1);len=0;
    for(int i=1;i<=n;i++)
        if(i==1||arr[i]!=arr[i-1])arr[++len]=arr[i];
}
inline int get(int d)
{
    int l=1,r=len;
    while(l<r)
    {
        int mid=l+r>>1;
        if(arr[mid]<d)l=mid+1;
        else r=mid;
    }
    return l;
}
struct HGTSeg{int l,r,s;}t[N*20];int cnt,root[N];
void update(int l,int r,int &x,int y,int pos)
{
    t[x=++cnt]=t[y];++t[x].s;
    if(l==r)return ;
    int mid=l+r>>1;
    if(pos<=mid)update(l,mid,t[x].l,t[y].l,pos);
    else update(mid+1,r,t[x].r,t[y].r,pos);
}
int query(int l,int r,int x,int y,int k)
{
    if(l==r)return l;
    int mid=l+r>>1,sum=t[t[x].l].s-t[t[y].l].s;
    if(k<=sum)return query(l,mid,t[x].l,t[y].l,k);
    else return query(mid+1,r,t[x].r,t[y].r,k-sum);
}
int main()
{
    int m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(a[i]),arr[i]=a[i];
    disc();
    for(int i=1;i<=n;i++)a[i]=get(a[i]);
    for(int i=1;i<=n;i++)update(1,len,root[i],root[i-1],a[i]);
    for(int i=1,l,r,k;i<=m;i++)
    {
        qr(l),qr(r),qr(k);
        qw(arr[query(1,len,root[r],root[l-1],k)]);puts("");
    }
    return 0;
}