主席树模板
ｃｏｄｅ：
#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ #define PAUSE printf("Press Enter key to continue..."); fgetc(stdin); const int maxn=2e5+500; #define fi first #define se second typedef std::map<int,int>::iterator Mpit; int n,m,cnt; int a[maxn],v[maxn],rt[maxn]; std::map<int,int>Mp; /*==================Define Area================*/ namespace PersistentSegmentTree { struct node { int ls,rs,l,r; int val; }t[maxn<<6]; int tot; void Update(int o) { t[o].val=t[t[o].ls].val+t[t[o].rs].val; } void Build(int o,int l,int r) { t[o].l=l;t[o].r=r; if(l==r) return ; int mid=(l+r)>>1; Build(t[o].ls=++tot,l,mid); Build(t[o].rs=++tot,mid+1,r); return ; } void Modify(int newrt,int rt,int x,int v) { t[newrt]=t[rt]; if(t[newrt].l==t[newrt].r) { t[newrt].val+=v; return ; } if(x<=t[t[newrt].ls].r) Modify(t[newrt].ls=++tot,t[rt].ls,x,v); else Modify(t[newrt].rs=++tot,t[rt].rs,x,v); Update(newrt); } int Query(int Lrt,int Rrt,int l,int r,int k) { if(l==r) return v[l]; int mid=(l+r)>>1; int x=t[t[Rrt].ls].val-t[t[Lrt].ls].val; if(k<=x) return Query(t[Lrt].ls,t[Rrt].ls,l,mid,k); else return Query(t[Lrt].rs,t[Rrt].rs,mid+1,r,k-x); } } using namespace PersistentSegmentTree; int main() { read(n);read(m); for(int i=1;i<=n;i++) { read(a[i]); Mp[a[i]]=1; } for(Mpit it=Mp.begin();it!=Mp.end();++it) { v[++cnt]=it->fi;Mp[it->fi]=cnt; } for(int i=1;i<=n;i++) a[i]=Mp[a[i]]; Build(rt[0]==++tot,1,cnt); for(int i=1;i<=n;i++) { Modify(rt[i]=++tot,rt[i-1],a[i],1); } for(int i=1,l,r,k;i<=m;i++) { read(l);read(r);read(k); int ans=Query(rt[l-1],rt[r],1,cnt,k); printf("%d\n",ans); } return 0; }转载于:https://www.cnblogs.com/Apocrypha/p/9430655.html
相关资源：JAVA上百实例源码以及开源项目