【BZOJ3524】Couriers

题面

Description

给一个长度为(n)的序列(a)。(1le a[i]le 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,mle 500000)

---

分析

主席树维护权值线段树，直接在树上二分。

#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<ctime>
#define LL long long
#define inf 0x3f3f3f3f

using namespace std;

inline char nc(){
    /* 
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
    */return getchar();
}
  
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
  
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(char &x){
  for (x=nc();!(x=='('||x==')');x=nc());
}

inline int read(char *s)
{
    char c=nc();int len=1;
    for(;!(c=='('||c==')');c=nc()) if (c==EOF) return 0;
    for(;(c=='('||c==')');s[len++]=c,c=nc());
    s[len++]='';
    return len-2;
}
int wt,ss[19];
inline void print(int x){
    if (x<0) x=-x,putchar('-'); 
    if (!x) putchar(48); else {
    for (wt=0;x;ss[++wt]=x%10,x/=10);
    for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
    if (x<0) x=-x,putchar('-');
    if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int T,n,m,s,k,h[500010],b[500010],d[500010];
struct ST
{
    int lc,rc,sum;
}a[10000010];

void build(int l,int r,int x)
{
    s++;x=s;
    if (l==r) {a[x].lc=a[x].rc=0;return ;}
    int mid=(l+r)>>1;
    a[x].lc=s+1;build(l,mid,x);
    a[x].rc=s+1;build(mid+1,r,x);
}

void change(int x,int y,int z,int xx,int l,int r)     //新结点编号,,,对应结点编号,[l,r]
{
    if (l==r) {a[x].sum=a[xx].sum+z;return ;}
    int mid=(l+r)>>1;
    if (y<=mid)
    {
        a[x].rc=a[xx].rc;
        s++;a[x].lc=s;
        change(s,y,z,a[xx].lc,l,mid);
    }
    else
    {
        a[x].lc=a[xx].lc;
        s++;a[x].rc=s;
        change(s,y,z,a[xx].rc,mid+1,r);
    }
    a[x].sum=a[a[x].lc].sum+a[a[x].rc].sum;
}

int query(int x,int y,int z,int l,int r)
{
    //printf("%d %d %d %d
",l,r,z,a[y].sum-a[x].sum);
    if (l==r)
    {
        if (a[y].sum-a[x].sum>z) return b[l];
        else return 0;
    }
    if (a[a[y].lc].sum-a[a[x].lc].sum>z) return query(a[x].lc,a[y].lc,z,l,(l+r)>>1);
    else if (a[a[y].rc].sum-a[a[x].rc].sum>z) return query(a[x].rc,a[y].rc,z,((l+r)>>1)+1,r);
    else return 0;
}

int main()
{
    read(n);read(m);
    memset(a,0,sizeof(a));
    for (int i=1;i<=n;i++)
        read(d[i]),b[i]=i;
    s=0;
    build(1,n,1);
    h[0]=1;
    for (int i=1;i<=n;i++)
    {
        s++;h[i]=s;
        change(s,d[i],1,h[i-1],1,n); 
    }
    int x,y,z;
    while(m--)
    {
        read(x);read(y);
        print(query(h[x-1],h[y],(y-x+1)/2,1,n));putchar('
');
    }
    return 0;
}