[POJ 2104]K-th Number
转载请注明出处：http://danihao123.is-programmer.com/
我擦终于A了这题了！
主席树坑点多……
最好不要写指针主席树，不然容易TLE……（自带常数？）
并且注意，一定要把数组开大，开大，再开大，重要的事情说三遍
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include <cstdio>#include <algorithm>using namespace std;const int maxn=100001,maxnode=maxn*20;int sumv[maxnode];int lc[maxnode];int rc[maxnode];int root[maxn];int A[maxn];int A2[maxn];int size,tot=0;int build_tree(int L,int R){ ++tot; if(L==R) return tot; int ans=tot,M=L+(R-L)/2; lc[ans]=build_tree(L,M); rc[ans]=build_tree(M+1,R); return ans;}int p;int update(int o,int L,int R){ int roo=++tot; sumv[roo]=sumv[o]; lc[roo]=lc[o]; rc[roo]=rc[o]; if(R>L){ int M=L+(R-L)/2; if(p<=M) lc[roo]=update(lc[tot],L,M); else rc[roo]=update(rc[tot],M+1,R); } sumv[roo]++; return roo;}int query(int lo,int ro,int L,int R,int k){ if(L==R) return L; int M=L+(R-L)/2,lc_siz=sumv[lc[ro]]-sumv[lc[lo]]; if(k<=lc_siz) return query(lc[lo],lc[ro],L,M,k); else return query(rc[lo],rc[ro],M+1,R,k-lc_siz);}void init_tree(int n){ register int i; sort(A2,A2+n); size=unique(A2,A2+n)-A2; root[0]=build_tree(1,size); for(i=1;i<=n;i++){ p=lower_bound(A2,A2+size,A[i-1])-A2+1; root[i]=update(root[i-1],1,size); }}int main(){ int n,m,u,v,k; register int i; scanf("%d%d",&n,&m); for(i=0;i<n;i++){ scanf("%d",&A[i]); A2[i]=A[i]; } init_tree(n); for(i=0;i<m;i++){ scanf("%d%d%d",&u,&v,&k); printf("%d\n",A2[query(root[u-1],root[v],1,size,k)-1]); } return 0;} |
评论 (0)
