BZOJ 3524: [Poi2014]Couriers [主席树]

2022-02-08 01:01:48

3524: [Poi2014]Couriers

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 1892 Solved: 683
[Submit][Status][Discuss]

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

复习一下普通主席树http://www.cnblogs.com/candy99/p/6160704.html

如何找出现次数大于(r-l+1)/2的数呢？

kth的过程中k不减就可以了，因为就是需要找一个叶子节点size>(r-l+1)/2

注意：本题数有重复，需要离散化去重

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=5e5+;

int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,mp[N],m,l,r,a[N];

int Bin(int v){

    int l=,r=m;

    while(l<=r){

        int mid=(l+r)>>;

        if(v==mp[mid]) return mid;

        if(v<mp[mid]) r=mid-;

        else l=mid+;

    }

    return ;

}

struct node{

    int lc,rc,size;

}t[N*];

int sz,root[N];

void ins(int &x,int l,int r,int num){

    sz++;

    t[sz]=t[x];x=sz;

    ++t[x].size;

    if(l==r) return;

    int mid=(l+r)>>;

    if(num<=mid) ins(t[x].lc,l,mid,num);

    else ins(t[x].rc,mid+,r,num);

}

int query(int i,int j,int k){//cishu>k

    int l=,r=m;

    while(l!=r){

        int mid=(l+r)>>;

        if(t[t[j].lc].size-t[t[i].lc].size>k) r=mid,i=t[i].lc,j=t[j].lc;

        else if(t[t[j].rc].size-t[t[i].rc].size>k) l=mid+,i=t[i].rc,j=t[j].rc;

        else return ;

    }

    return l;

}

int main(){

    //freopen("in.txt","r",stdin);

    n=read();Q=read();

    for(int i=;i<=n;i++) mp[++m]=a[i]=read();

    sort(mp+,mp++m);

    int p=;

    for(int i=;i<=m;i++) if(mp[i]!=mp[i-]) mp[++p]=mp[i];

    m=p;

    for(int i=;i<=n;i++) root[i]=root[i-],ins(root[i],,m,Bin(a[i]));

    while(Q--) l=read(),r=read(),printf("%d\n",mp[query(root[l-],root[r],(r-l+)/)]);

}

码农公寓