BZOJ3524: [Poi2014]Couriers-布布扣-bubuko.com

Description

给一个长度为n的序列a。1≤a[i]≤n。
m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。

Input

第一行两个数n，m。
第二行n个数，a[i]。
接下来m行，每行两个数l,r，表示询问[l,r]这个区间。

Output

m行，每行对应一个答案。

Sample Input

7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6

Sample Output

1
0
3
0
4

HINT

【数据范围】

n,m≤500000

2016.7.9重设空间，但未重测！

Source

By Dzy

觉得挺值得说一下的，学习到了

首先从思路来讲，我们可以使用主席树，来维护查询区间内每个数出现的次数

如何利用这个出现次数来解决答案呢？

要反过来利用答案的性质，num*2>(r-l+1)的数只有这一个

而如果这样一个数是存在的话，其他数出现次数的加和的二倍也会小于(r-l+1)

因此考虑在树上二分，如果l到mid的总和的二倍大于了长度，那么答案一定来自左边（或者不存在

右边的同理，如果两边都不满足就是0了

顺带一提，这道题如果想把内存卡在128mb以内的话，刚开始那颗空树就不要建（话说为什么要建啊

因为空树的结构并不是很重要，只要让sum值都是0即可，所以T[0]=0也挺好的

这样节省的空间就能卡进128了2333333（真是学习了

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define N 500010
 4 #define mid (l+r)/2
 5 using namespace std;
 6 int n,q,a[N],cnt;
 7 int sum[10000010],L[10000010],R[10000010],T[N];
 8 int update(int pre,int l,int r,int x){
 9     int rt=++cnt;
10     L[rt]=L[pre];R[rt]=R[pre];sum[rt]=sum[pre]+1;
11     if(l<r){
12         if(x<=mid)L[rt]=update(L[pre],l,mid,x);
13         else R[rt]=update(R[pre],mid+1,r,x);
14     }
15     return rt;
16 }
17 int query(int u,int v,int l,int r,int len){
18     if(l>=r)return l;
19     if((sum[L[v]]-sum[L[u]])*2>len)return query(L[u],L[v],l,mid,len);
20     else if((sum[R[v]]-sum[R[u]])*2>len)return query(R[u],R[v],mid+1,r,len);
21     else return 0;
22 }
23 int main(){
24     scanf("%d%d",&n,&q);
25     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
26     T[0]=0;
27     for(int i=1;i<=n;i++){
28         T[i]=update(T[i-1],1,n,a[i]);
29     }
30     for(int i=1,x,y;i<=q;i++){
31         scanf("%d%d",&x,&y);
32         printf("%d\n",query(T[x-1],T[y],1,n,y-x+1));
33     }
34     return 0;
35 }

View Code

BZOJ3524: [Poi2014]Couriers

原文：https://www.cnblogs.com/2017SSY/p/10458516.html