開始用线段树+归并排序，4700+ms飘过~，后来去学划分树。尽管还不是非常懂，只是就这样吧

#include
      
       #include
       
        #define maxn 100010using namespace std;int n,m;int nsort[maxn];int nleft[30][maxn],tree[30][maxn];void build(int l,int r,int c){	if(l==r) return;	int mid=(l+r)/2;	int sum=mid-l+1;	for(int i=l;i<=r;i++)	{		if(tree[c][i]
        
         0) tree[c+1][ll++]=tree[c][i],sum--;		else tree[c+1][rr++]=tree[c][i];		nleft[c][i]=nleft[c][l-1]+ll-l;	}	build(l,mid,c+1);	build(mid+1,r,c+1);}int que(int l,int r,int a,int b,int k,int c){	if(a==b) return tree[c][a];	int mid=(l+r)/2;	int cnt=nleft[c][b]-nleft[c][a-1];	if(cnt>=k)	{		int nl=l+nleft[c][a-1]-nleft[c][l-1];		int nr=nl+cnt-1;		return que(l,mid,nl,nr,k,c+1);	}	else 	{		int nr=b+nleft[c][r]-nleft[c][b];        int nl=nr-(b-a-cnt);        return que(mid+1,r,nl,nr,k-cnt,c+1);	}}int main(){	cin.sync_with_stdio(false);	int t;	cin>>t;	while(t--)	{		cin>>n>>m;		for(int i=1;i<=n;i++)		{			cin>>tree[0][i];			nsort[i]=tree[0][i];		}		sort(nsort+1,nsort+n+1);		build(1,n,0);//l,r,层。 		while(m--)		{			int a,b,k;			cin>>a>>b>>k;			cout<
         
          <