C++(g++ 7.5.0) 解法, 执行用时: 176ms, 内存消耗: 4168K, 提交时间: 2023-01-20 18:25:21

#include<iostream>
using namespace std;

const int N=1e5+10,INF=1e9;
int n,m,t,c[N],ans[N];
struct rec{int op,x,y,z;}q[2*N],lq[2*N],rq[2*N];

int ask(int x)
{
    int toreturn=0;
    for(;x;x-=(x&-x)) toreturn+=c[x];
    return toreturn;
}

void add(int x,int y)
{
    for(;x<=n;x+=(x&-x)) c[x]+=y;
}

void solve(int lval,int rval,int st,int ed)
{
    if(st>ed) return;
    if(lval==rval)
    {
        for(int i=st;i<=ed;i++)
            if(q[i].op>0) ans[q[i].op]=lval;
        return;
    }
    int mid=(lval+rval)>>1;
    int lt=0,rt=0;
    for(int i=st;i<=ed;i++)
    {
        if(q[i].op==0)
        {
            if(q[i].y<=mid) add(q[i].x,1),lq[++lt]=q[i];
            else rq[++rt]=q[i];
        }
        else
        {
            int cnt=ask(q[i].y)-ask(q[i].x-1);
            if(cnt>=q[i].z) lq[++lt]=q[i];
            else q[i].z-=cnt,rq[++rt]=q[i]; 
        }
    }
    for(int i=ed;i>=st;i--)
        if(q[i].op==0&&q[i].y<=mid) add(q[i].x,-1);
    for(int i=1;i<=lt;i++) q[st+i-1]=lq[i];
    for(int i=1;i<=rt;i++) q[st+lt+i-1]=rq[i];
    solve(lval,mid,st,st+lt-1);
    solve(mid+1,rval,st+lt,ed); 
}

int main(void)
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int temp;
        cin>>temp;
        q[++t].op=0,q[t].x=i,q[t].y=temp;
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        cin>>l>>r>>k;
        q[++t].op=i,q[t].x=l,q[t].y=r,q[t].z=k;
    }
    solve(-INF,INF,1,t);
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 93ms, 内存消耗: 38676K, 提交时间: 2020-09-09 13:25:17

#include<cstdio>

const int INF=1e9+1,M=1e5+10,N=50e5+10;
int v,op,t=0;
int d[M],tot[N],root[M],ls[N],rs[N];


void ins(int x,int &now,int l,int r)
{
	if(!now)now=++t;
	tot[now]=op+tot[x];
	int mid=(l+r)>>1;
	if(l==r)return ;
	if(v<=mid)
	{
		rs[now]=rs[x];
		ins(ls[x],ls[now],l,mid);
	}
	else
	{
		ls[now]=ls[x];
		ins(rs[x],rs[now],mid+1,r);
	}
}

int temp,l,r;

int findk(int x,int y,int k)
{
	int xx=root[x-1],yy=root[y];
	l=-INF;r=INF;
	while(l<r)
	{
		int mid=(l+r)>>1;//向下取整 
		temp=tot[ls[yy]]-tot[ls[xx]];
		if(k<=temp)
		{
			xx=ls[xx];yy=ls[yy];
			r=mid;
		}
		else
		{
			yy=rs[yy];xx=rs[xx];
			k-=temp;
			l=mid+1;
		}
	}
	return l;
}

int main()
{
	int n,m;scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&d[i]);
		v=d[i];op=1;
		ins(root[i-1],root[i],-INF,INF);
	}
	
	for(int i=1;i<=m;i++)
	{
		int x,y,c;scanf("%d %d %d",&x,&y,&c);
		printf("%d\n",findk(x,y,c));
	}
	return 0;
}