试着用vector动态开点,然而连biuld都炸了,debug、百度无果,求大佬指教:
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while('0'<=ch&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,m;
int a[200050],a2[200050];
struct node{
int ls,rs;
int sum;
};
vector<node>tr;
int biuld(int l,int r){
tr.push_back((node){1,1,1});
if(l==r)return 0;
int now=tr.size()-1,mid=(l+r)>>1;
tr[now].ls=biuld(l,mid);
tr[now].rs=biuld(mid+1,r);
return now;
}
int update(int u,int l,int r,int k){
tr.push_back((node){tr[u].ls,tr[u].rs,0});
int now=tr.size()-1;
if(l==r){
tr[now].sum=1;
return now;
}
int mid=(l+r)>>1;
if(k<=mid) tr[now].ls=update(tr[u].ls,l,mid,k);
else tr[now].rs=update(tr[u].rs,mid+1,r,k);
tr[now].sum=tr[tr[now].ls].sum+tr[tr[now].rs].sum;
}
int ask(int u,int v,int l,int r,int k){
if(l==r)return a2[l];
int mid=(r+l)>>1;
if(tr[tr[u].ls].sum-tr[tr[v].ls].sum>=k)return ask(tr[u].ls,tr[v].ls,l,mid,k);
else return ask(tr[u].rs,tr[v].rs,mid+1,r,k-(tr[tr[u].ls].sum-tr[tr[v].ls].sum));
}
int rt[200050];
int main() {
scanf("%d%d",&n,&m);
biuld(1,n);
for(int i=1;i<=n;i++)a[i]=read(),a2[i]=a[i];
sort(a2+1,a2+n+1);
int len=unique(a2+1,a2+n+1)-a2;
for(int i=1;i<=n;i++)a[i]=lower_bound(a2+1,a2+len,a[i])-a2;
rt[0]=1;
for(int i=1;i<=n;i++)rt[i]=update(rt[i-1],1,n,a[i]);
int l,r,k;
while(m--){
l=read();
r=read();
k=read();
printf("%d\n",ask(rt[r],rt[l-1],1,n,k));
}
return 0;
}