[bzoj 3524 / 2223] [Poi 2014] Couriers / [Coci 2009] PATULJCI 의장 트 리

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
주석 나 무 를 만 든 후 구간 내 좌우 로 저쪽 이 렌 / 2 보다 크 면 되 는데...
이 바보 X 는 다 시 는 지침 판 을 쓰 지 않 을 것 이다. 카드 공간 카드 의 죽은... 1kw 의 배열 이 야 말로 충분 하 다.....................................................
참고 로 bzoj 2223 의 좋 은 귀 축 읽 기

#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int SZ = 500010;
const int INF = 1000000010;
const double eps = 1e-6;

int n,m;

struct node{
    int l,r;
    int cnt;
}tree[10000010];

int rt[SZ];

int Tcnt = 0;

void insert(int l,int r,int last,int &now,int x)
{
    now = ++ Tcnt;
    tree[now] = tree[last];
    tree[now].cnt = tree[last].cnt + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(x <= mid) insert(l,mid,tree[last].l,tree[now].l,x);
    else insert(mid + 1,r,tree[last].r,tree[now].r,x);
}

int ask(int l,int r)
{
    int len = r - l + 1 >> 1;
    int p = rt[l - 1];
    int q = rt[r];
    int s = 1,t = n;
    if(tree[q].cnt - tree[p].cnt <= len) return 0;
    while(s != t)
    {
        int mid = s + t >> 1;
        if(tree[tree[q].l].cnt - tree[tree[p].l].cnt > len)
            q = tree[q].l,p = tree[p].l,t = mid;
        else if(tree[tree[q].r].cnt - tree[tree[p].r].cnt > len)
            q = tree[q].r,p = tree[p].r,s = mid + 1;
        else
            return 0;
    }
    return s;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
    {
        int x;
        scanf("%d",&x);
        insert(1,n,rt[i - 1],rt[i],x);
    }
    for(int i = 1;i <= m;i ++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d
",ask(l,r));
    }
    return 0;
}

#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;
const int SZ = 500010;
const int INF = 1000000010;
const double eps = 1e-6;

int n,m,L;

struct node{
    int l,r;
    int cnt;
}tree[10000010];

int rt[SZ];

int Tcnt = 0;

void insert(int l,int r,int last,int &now,int x)
{
    now = ++ Tcnt;
    tree[now] = tree[last];
    tree[now].cnt = tree[last].cnt + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(x <= mid) insert(l,mid,tree[last].l,tree[now].l,x);
    else insert(mid + 1,r,tree[last].r,tree[now].r,x);
}

int ask(int l,int r)
{
    int len = r - l + 1 >> 1;
    int p = rt[l - 1];
    int q = rt[r];
    int s = 1,t = L;
    if(tree[q].cnt - tree[p].cnt <= len) return 0;
    while(s != t)
    {
        int mid = s + t >> 1;
        if(tree[tree[q].l].cnt - tree[tree[p].l].cnt > len)
            q = tree[q].l,p = tree[p].l,t = mid;
        else if(tree[tree[q].r].cnt - tree[tree[p].r].cnt > len)
            q = tree[q].r,p = tree[p].r,s = mid + 1;
        else
            return 0;
    }
    return s;
}

int main()
{
    scanf("%d%d",&n,&L);
    for(int i = 1;i <= n;i ++)
    {
        int x;
        scanf("%d",&x);
        insert(1,L,rt[i - 1],rt[i],x);
    }
    int q;
    scanf("%d",&q);
    for(int i = 1;i <= q;i ++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int ans = ask(l,r);
        if(ans == 0) puts("no");
        else printf("yes %d
",ans);
    }
    return 0;
}