技巧一：离散去重
for(int i=1;i<=n;i++) scanf("%d",&a[i] ),b[i]=a[i]; sort(b+1,b+n+1); int nn=unique(b+1,b+n+1)-b-1;//假设有x个数，那么nn指针会停在第x+1个数的位置 ，nn及以后的都是重复的元素for(int i=1;i<=n;i++) id[i]=lower_bound(b+1,b+nn+1,a[i])-b;//离散过后的新value
技巧二：可持久化数据结构
修改被影响的部分，然后用指针指向新的点，记录新的点，就可以方便查找了
void updata(int l,int r,int &nw,int pre,int x) { nw=++cnt; t[nw]=t[pre];t[nw].sum ++; if(l==r) return ; int mid=(l+r)>>1; if(mid>=x) updata(l,mid,t[nw].lc ,t[pre].lc ,x); else updata(mid+1,r,t[nw].rc ,t[pre].rc ,x); }
技巧三：区间问题一般都可以被拆成a[R]-a[L-1]
即使每个a有N个分支
int query(int l,int r,int ll,int rr,int kk) { if(l==r) return l; int s=t[t[rr].lc ].sum -t[t[ll].lc ].sum ; int mid=(l+r)>>1; if(s>=kk) return query(l,mid,t[ll].lc ,t[rr].lc ,kk); else return query(mid+1,r,t[ll].rc ,t[rr].rc ,kk-s); }
最后：主席树模板
//luogu P3834 #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,m; const int N=200003; int a[N],b[N],id[N]; struct node { int sum,lc,rc; }t[N*40]; int cnt,rt[N]; int build(int l,int r) { int rt=++cnt; t[rt].sum =0; if(l!=r) { int mid=(l+r)>>1; t[rt].lc =build(l,mid); t[rt].rc =build(mid+1,r); } return rt; } void updata(int l,int r,int &nw,int pre,int x) { nw=++cnt; t[nw]=t[pre];t[nw].sum ++; if(l==r) return ; int mid=(l+r)>>1; if(mid>=x) updata(l,mid,t[nw].lc ,t[pre].lc ,x); else updata(mid+1,r,t[nw].rc ,t[pre].rc ,x); } int query(int l,int r,int ll,int rr,int kk) { if(l==r) return l; int s=t[t[rr].lc ].sum -t[t[ll].lc ].sum ; int mid=(l+r)>>1; if(s>=kk) return query(l,mid,t[ll].lc ,t[rr].lc ,kk); else return query(mid+1,r,t[ll].rc ,t[rr].rc ,kk-s); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i] ),b[i]=a[i]; sort(b+1,b+n+1); int nn=unique(b+1,b+n+1)-b-1;//假设有x个数，那么nn指针会停在第x+1个数的位置 //去重，离散 rt[0]=build(1,nn); for(int i=1;i<=n;i++) { id[i]=lower_bound(b+1,b+nn+1,a[i])-b; updata(1,nn,rt[i],rt[i-1],id[i]);//需要a数组的数到序号的离散 }//离散过后的新value int x,y,k; while(m--) { scanf("%d%d%d",&x,&y,&k); printf("%d ",b[ query(1,nn,rt[x-1],rt[y],k) ]);//需要序号到b数组的离散 } return 0; }