想明白原理的点:https://blog.csdn.net/ModestCoder_/article/details/90107874
列题:洛谷P3834
代码:
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
x=0; register char c=getchar(); register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
const int maxn=200005;
struct node
{
int l,r,val;
}e[maxn*35];
int a[maxn],cnt,n,m;
int root[maxn];
vector<int> v;
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void update(int l,int r,int &x,int y,int pos)
{
e[++cnt]=e[y];
e[cnt].val++;
x=cnt;
if(l==r){return;}
int mid=(l+r)/2;
if(pos<=mid){update(l,mid,e[x].l,e[y].l,pos);}
else{update(mid+1,r,e[x].r,e[y].r,pos);}
}
int query(int l,int r,int x,int y,int k)
{
if(l==r){return l;}
int mid=(l+r)/2;
int sum=e[e[y].l].val-e[e[x].l].val;
if(k<=sum){return query(l,mid,e[x].l,e[y].l,k);}
else{return query(mid+1,r,e[x].r,e[y].r,k-sum);}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
v.pb(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++)
{
update(1,n,root[i],root[i-1],getid(a[i]));
}
while(m--)
{
int l,r,k;
scanf("%d %d %d",&l,&r,&k);
printf("%d\n",v[query(1,n,root[l-1],root[r],k)-1]);
}
return 0;
}