【bzoj3524】[Poi2014]Couriers

2015.05.20 09:34 Wed | 4次阅读 | 旧日oi | 固定链接 | 源码

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

题解

用主席树很巧妙的应用了出现的次数大于(r-l+1)/2这个性质,建立主席树后,对一个询问,如果存在这样的数,只可能存在一个,所以这个数不是在左边就是在右边,或者不存在,于是我们就可以二分答案了

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,cnt;
int root[500001];
int sum[500001*20],ls[500001*20],rs[500001*20];
void build(int l,int r,int t,int &x,int v)
{
    sum[x=++cnt]=sum[t]+1;
    int mid=(l+r)>>1;
    if(l==r) return;
    if(v<=mid) rs[x]=rs[t],build(l,mid,ls[t],ls[x],v);
    else ls[x]=ls[t],build(mid+1,r,rs[t],rs[x],v);
}
int query(int L,int R)
{
    int l=1,r=n,mid,x=root[L-1],y=root[R],tmp=(R-L+1)/2;
    while(l!=r)
    {
        if(sum[y]-sum[x]<=tmp) return 0;
        mid=(l+r)>>1;
        if(sum[ls[y]]-sum[ls[x]]>tmp) r=mid,x=ls[x],y=ls[y];
        else if(sum[rs[y]]-sum[rs[x]]>tmp) l=mid+1,x=rs[x],y=rs[y];
        else return 0;
    }
    return l;
}
int main()
{
    cin>>n>>m;
    for(int x,i=1;i<=n;i++)
    {
        scanf("%d",&x);
        build(1,n,root[i-1],root[i],x);
    }
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",query(x,y));
    }
}```