几个月没打了...全忘光
记得之前写过一篇主席树入门教程 https://blog.csdn.net/Patrickpwq/article/details/80315358
显然里面的代码丑的不能看
重发一个代码
主席树推荐不要写结构体
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define N 200005 using namespace std; int n,m,a[N],b[N],p,q,rt[N<<5],tot,sum[N<<5],lc[N<<5],rc[N<<5]; void build(int &now,int l,int r) { now=++tot; if(l==r) return; int mid=(l+r)>>1; build(lc[now],l,mid); build(rc[now],mid+1,r); } int update(int now,int l,int r) { int newnode=++tot; lc[newnode]=lc[now]; rc[newnode]=rc[now]; sum[newnode]=sum[now]+1; if(l==r) return newnode; int mid=(l+r)>>1; if(p<=mid) lc[newnode]=update(lc[newnode],l,mid); else rc[newnode]=update(rc[newnode],mid+1,r); return newnode; } int query(int x,int y,int l,int r,int k) { if(l==r) return l; int mid=((l+r)>>1),ans,delta=sum[lc[y]]-sum[lc[x]]; if(k<=delta) ans=query(lc[x],lc[y],l,mid,k); else ans=query(rc[x],rc[y],mid+1,r,k-delta); return ans; } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]; } sort(b+1,b+n+1); q=unique(b+1,b+n+1)-b-1; build(rt[0],1,q); //基础主席树 for(int i=1;i<=n;i++) { p=lower_bound(b+1,b+q+1,a[i])-b; rt[i]=update(rt[i-1],1,q); } for(int i=1;i<=m;i++) { int l,r,k; cin>>l>>r>>k; cout<<b[query(rt[l-1],rt[r],1,q,k)]<<endl; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9800507.html
相关资源：各显卡算力对照表！