首页 > 代码库 > 【bzoj3524】[Poi2014]Couriers
【bzoj3524】[Poi2014]Couriers
题目描述
给一个长度为n的序列a。1≤a[i]≤n。
m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。
输入
第一行两个数n,m。
第二行n个数,a[i]。
接下来m行,每行两个数l,r,表示询问[l,r]这个区间。
输出
m行,每行对应一个答案。
样例输入
7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
样例输出
1
0
3
0
4
题解
主席树
同bzoj2223,也不需要离散化。
bzoj2223题解:http://www.cnblogs.com/GXZlegend/p/6292609.html
1 #include <cstdio> 2 int si[10000010] , lp[10000010] , rp[10000010] , root[500010] , tot; 3 void pushup(int x) 4 { 5 si[x] = si[lp[x]] + si[rp[x]]; 6 } 7 void ins(int x , int &y , int l , int r , int p) 8 { 9 y = ++tot; 10 if(l == r) 11 { 12 si[y] = si[x] + 1; 13 return; 14 } 15 int mid = (l + r) >> 1; 16 if(p <= mid) rp[y] = rp[x] , ins(lp[x] , lp[y] , l , mid , p); 17 else lp[y] = lp[x] , ins(rp[x] , rp[y] , mid + 1 , r , p); 18 pushup(y); 19 } 20 int query(int x , int y , int l , int r , int p) 21 { 22 if(l == r) return l; 23 int mid = (l + r) >> 1; 24 if(si[lp[y]] - si[lp[x]] > p) return query(lp[x] , lp[y] , l , mid , p); 25 if(si[rp[y]] - si[rp[x]] > p) return query(rp[x] , rp[y] , mid + 1 , r , p); 26 return 0; 27 } 28 int main() 29 { 30 int n , m , i , a , b; 31 scanf("%d%d" , &n , &m); 32 for(i = 1 ; i <= n ; i ++ ) 33 { 34 scanf("%d" , &a); 35 ins(root[i - 1] , root[i] , 1 , n , a); 36 } 37 while(m -- ) 38 { 39 scanf("%d%d" , &a , &b); 40 printf("%d\n" , query(root[a - 1] , root[b] , 1 , n , (b - a + 1) >> 1)); 41 } 42 return 0; 43 }
【bzoj3524】[Poi2014]Couriers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。