題意：

給定一個序列，求[a,b]區間第k大的數字。

思路：

主席樹模板題，但是注意數據范圍，需要離散化。

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm>#define w(i) T[(i)].w #define ls(i) T[(i)].ls #define rs(i) T[(i)].rs using namespace std; const int MAXNN=100005;struct NUM {int a,rank; }num[MAXNN];int cmp(NUM a,NUM b) {return a.a<b.a; }struct node {int ls,rs,w;node(){ls=rs=w=0;} } T[MAXNN*20]; int root[MAXNN],sz,m; int a[MAXNN];void ins(int &i,int l,int r,int x) {T[++sz]=T[i];i=sz;w(i)++;if (l==r) return;int m=(l+r)>>1;if (x<=m) ins(ls(i),l,m,x);else ins(rs(i),m+1,r,x); } int query(int i,int j,int l,int r,int k) {if (l==r) return l;int t=w(ls(j))-w(ls(i));int m=(l+r)>>1;if (t>=k) return query(ls(i),ls(j),l,m,k);else return query(rs(i),rs(j),m+1,r,k-t); } int aa[MAXNN]; int bb[MAXNN]; int main() {//DO YOLOint n,m;while(scanf("%d%d",&n,&m)!=EOF){root[0]=0;sz=0;memset(num,0,sizeof(num));for (int i=1; i<=n; i++){scanf("%d",&num[i].a);num[i].rank=i;bb[i] = aa[i] = num[i].a;}sort(num+1,num+1+n,cmp);sort(bb+1, bb+1+n);memset(a,0,sizeof(a));for(int i=1;i<=n;i++)a[num[i].rank]=i;for(int i=1;i<=n;i++){root[i]=root[i-1];//int pos = lower_bound(bb+1, bb+1+n, aa[i]) - bb;ins(root[i],1,n, a[i]);}for(int i=1; i<=m; i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);//int pos = query(root[a-1], root[b], 1, n, c);//printf("%d\n", bb[pos]);int ans=query(root[a-1],root[b],1,n,c);printf("%d\n",num[ans].a);}//QUERY(s,t,k):query(root[s-1],root[T],1,n,k);}return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的poj2104(区间第k大+离散化)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。