[BZOJ 3524]Couriers
转载请注明出处：http://danihao123.is-programmer.com/
这道题有了主席树，就是裸题了……
只要用主席树维护出现次数，然后二分求解即可
但是！数组一定要开大，开大，再开大，重要的事情说三遍！
代码：
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 71 72 73 74 75 76 77 78 79 80 | /************************************************************** Problem: 3524 User: danihao123 Language: C++ Result: Accepted Time:6432 ms Memory:129712 kb****************************************************************/ #include <cstdio>#include <algorithm>using namespace std;const int maxn=500001,maxnode=maxn*21;int sumv[maxnode];int lc[maxnode];int rc[maxnode];int root[maxn];int A[maxn],A2[maxn];int size,cnt=0;int build_tree(int L,int R){ int ans=++cnt; if(L==R) return ans; int 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=++cnt; 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[roo],L,M); else rc[roo]=update(rc[roo],M+1,R); } sumv[roo]++; return roo;}int ql,qr;int query(int lo,int ro,int L,int R){ if(L==R){ return A2[L-1]; } int M=L+(R-L)/2,lc_siz=sumv[lc[ro]]-sumv[lc[lo]],rc_siz=sumv[rc[ro]]-sumv[rc[lo]]; if(lc_siz>((qr-ql+1)/2)) return query(lc[lo],lc[ro],L,M); if(rc_siz>((qr-ql+1)/2)) return query(rc[lo],rc[ro],M+1,R); return 0;}void init_tree(int n){ sort(A2,A2+n); size=unique(A2,A2+n)-A2; root[0]=build_tree(1,size); for(register int 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; 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",&ql,&qr); printf("%d\n",query(root[ql-1],root[qr],1,size)); } return 0;} |
评论 (0)
