一个玄学问题

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,ans[N];
map<int,int>mp,rm;//离散化
int ct;//同上
struct node
{
	int val,id;
}a[N];
bool cmp(node x,node y)
{
	return x.val<y.val;
}
struct operation//操作
{
    int L,R;   // 对于查询操作表示查询区间[L,R]，对于插入操作表示数值的离散化编号
    int id;    // 操作标识：对于查询是查询编号，对于插入是元素位置
    int k;     // 查询的第k小值
    int type;  // 操作类型：1=插入，2=查询
}b[N];
int s;//操作总数
operation opl[N],opr[N];//左半、右半操作
int ctl,ctr;//左半、右半操作数量
int tr[N];//这个树状数组的作用是查统计区间内元素个数 
int lowbit(int x)
{
	return x&(-x);
}
int query(int x)//查询树状数组：前缀和 [1~x]
{
	int res=0;
	while(x)
	{
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
void add(int x,int w)//更新树状数组：在位置 x 增加 w
{
	while(x<=n)
	{
		tr[x]+=w;
		x+=lowbit(x);
	}
}
void solve(int l,int r,int ql,int qr)//[l~r]为值域（离散化后的），[ql~qr] 为操作范围（在数组 b 中的）
{
	if(ql>qr)return;//没得操了
	if(l==r)
	{
		for(int i=ql; i<=qr; i++)
			if(b[i].type==2)ans[b[i].id]=rm[l];//记录答案(使用反向映射获取原始值)
		return;
	}
	int mid=(l+r)>>1;
	ctl=ctr=0;
	for(int i=ql; i<=qr; i++)
		if(b[i].type==1)//插入 
			if(b[i].L<=mid)// 
			{
				add(b[i].id,1);
				opl[++ctl]=b[i];
			}
			else opr[++ctr]=b[i];
		else//查询 
		{
			int x=query(b[i].R)-query(b[i].L-1);
			if(b[i].k>x)b[i].k-=x,opr[++ctr]=b[i];
			else opl[++ctl]=b[i];
		}
	for(int i=1; i<=ctl; i++)
		if(opl[i].type==1)add(opl[i].id,-1);//清空树状数组 
	for(int i=1; i<=ctl; i++)//将临时数组合并回原数组
		b[i+ql-1]=opl[i];
	for(int i=1; i<=ctr; i++)//同上 
		b[i+ctl+ql-1]=opr[i];
	solve(l,mid,ql,ctl+ql-1);
	solve(mid+1,r,ctl+ql,qr);
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i].val;
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1; i<=n; i++)//离散化 
	{
		if(!mp[a[i].val])mp[a[i].val]=++ct,rm[ct]=a[i].val;
		b[++s]={mp[a[i].val],-1,a[i].id,-1,1};
	}
	for(int i=1; i<=m; i++)
	{
		int x,y,k;
		cin>>x>>y>>k;
		b[++s]={x,y,i,k,2};
	}
	solve(0,ct+1,1,s);
	for(int i=1; i<=m; i++)
		cout<<ans[i]<<'\n';
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int ans[N],n,m,cnt;
map<int,int>hash_,rh;
struct node
{
    int val;
    int pos;
}a[N];
struct qurr
{
    int L,R,id,k,type;
}b[N];
int s;
qurr q1[N],q2[N];
int cnt1,cnt2;
int tr[N];
int tt;
bool cmp(node x,node y)
{
    return x.val<y.val;
}
int qur(int p)
{
    int ans=0;
    while(p)
	{
        ans+=tr[p];
        p-=p&(-p);
    }
    return ans;
}
void add(int p,int x)
{
    while(p<=n)
	{
        tr[p]+=x;
        p+=p&(-p);
    }
}
void solve(int l,int r,int ql,int qr)
{
    if(ql>qr)return;
    if(l==r)
	{
        for(int i=ql; i<=qr; i++)
            if(b[i].type==2)ans[b[i].id]=rh[l];
        return;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    for(int i=ql; i<=qr; i++)
	{
        if(b[i].type==1) 
		{
            if(b[i].L<=mid)
			{
			    add(b[i].id,1);
				q1[++cnt1]=b[i];
            }
            else q2[++cnt2]=b[i];
      	}
      	else
		{
          int x=b[i].L,y=b[i].R;
          int tem=qur(y)-qur(x-1);
          if (b[i].k>tem)b[i].k-=tem,q2[++cnt2]=b[i];
          else q1[++cnt1]=b[i];
      	}
  	}
	for(int i=1; i<=cnt1; i++)
		if(q1[i].type==1)add(q1[i].id,-1);
	for(int i=1; i<=cnt1; i++)
	  	b[i+ql-1]=q1[i];
	for(int i=1; i<=cnt2; i++) 
		b[i+cnt1+ql-1]=q2[i];
	solve(l,mid,ql,cnt1+ql-1);	
	solve(mid+1,r,cnt1+ql,qr);
}
signed main(){
 	scanf("%d%d", &n, &m);
 	for (int i = 1; i <= n; i++)
	{
     	cin>>a[i].val;
     	a[i].pos=i;
	}
 	sort(a+1,a+n+1,cmp);
 	for(int i=1; i<=n; i++)
 	{
     	int tem=a[i].val;
     	if(!hash_[tem])
	 	{
         	hash_[tem]=++cnt;
         	rh[cnt]=tem;
     	}
     	b[++s]={hash_[tem],-1,a[i].pos,-1,1};
 	}
	for(int i=1; i<=m; i++) 
	{
     	int x,y,k;
     	cin>>x>>y>>k;
     	b[++s]={x,y,i,k,2};
 	}
 	solve(0,cnt+1,1,s);
 	for(int i=1; i<=m; i++)
    	cout<<ans[i]<<'\n';
 	return 0;
}