bzoj3524 [Poi2014]Couriers

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

Source

By Dzy

主席树模板题。
其实主席树就是线段树的节点连一连？

#include <bits/stdc++.h>
#define N 500010
#define M 10000010
using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch =  getchar();
    }
    return x * f;
}
struct xs
{
    int ls, rs, sum;
}t[M];
int n, m, sz, root[N];

void update(int l, int r, int x, int &y, int v)
{
    y = ++ sz;
    t[y].sum = t[x].sum + 1;
    if(l == r) return;
    t[y].ls = t[x].ls;
    t[y].rs = t[x].rs;
    int mid = (l + r) >> 1;
    if(v <= mid) update(l, mid, t[x].ls, t[y].ls, v);
    else update(mid + 1, r, t[x].rs, t[y].rs, v);
}


int query(int L, int R)
{
    int l = 1, r = n, mid, x, y, tmp = (R - L + 1) >> 1;
    x = root[L - 1];
    y = root[R];
    while(l != r)
    {
        if(t[y].sum - t[x].sum <= tmp) return 0;
        mid = (l + r) >> 1;
        if(t[ t[y].ls ].sum  - t[ t[x].ls ].sum > tmp)
            r = mid, x = t[x].ls, y = t[y].ls;
        else
            if(t[ t[y].rs ].sum - t[ t[x].rs ].sum > tmp)
            {
                l = mid + 1, x = t[x].rs, y = t[y].rs;
            }
            else return 0;
    }
    return l;
}

int main()
{
    n = read();
    m = read();
    for(int i = 1; i <= n; i ++)
    {
        int x = read();
        update(1, n, root[i - 1], root[i], x);
    }

    for(int i = 1; i <= m; i ++)
    {
        int l = read();
        int r = read();
        printf("%d\n", query(l, r));
    }

    return 0;
}