主席树模板题，但是是不带修改的QAQ
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;const int N=1e5+5;int n,m,x,y,z,sz,ans;int val[N],loc[N],num[N],root[N];struct seg{ int lch,rch,val;}tr[N*20];int cmp(const int &a,const int &b){return val[a]<val[b];}inline void build(int &now,int l,int r,int x){ int mid=(l+r)>>1; tr[++sz]=tr[now],now=sz; tr[now].val++; if(l==r)return ; if (x<=mid) build(tr[now].lch,l,mid,x); else build(tr[now].rch,mid+1,r,x);}inline int query(int i,int j,int l,int r,int k){ if (l==r)return l; int mid=(l+r)>>1; int t=tr[tr[j].lch].val-tr[tr[i].lch].val; if (t>=k)return query(tr[i].lch,tr[j].lch,l,mid,k); else return query(tr[i].rch,tr[j].rch,mid+1,r,k-t);}int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&val[i]),loc[i]=i; sort(loc+1,loc+n+1,cmp); for (int i=1;i<=n;i++) num[loc[i]]=i; sz=0;root[0]=0; for (int i=1;i<=n;i++) { root[i]=root[i-1]; build(root[i],1,n,num[i]); } for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); ans=query(root[x-1],root[y],1,n,z); PRintf("%d/n",val[loc[ans]]); }}新闻热点
疑难解答
