PATULJCI

Time Limit: 10 Sec Memory Limit: 259 MB

Description

img

Input

第一行两个整数n,INF，表示序列长度和ai的上限；
　　第二行有n个数，表示ai；
　　然后有一个整数m，表示询问个数；
　　接下来每行两个l,r，表示询问区间[l,r]中的答案。

Output

输出m行，表示对于每个询问的答案。如果有这个数，则输出“yes”，然后输出数的值；否则输出“no”。

Sample Input

10 3
　　1 2 1 2 1 2 3 2 3 3
　　8
　　1 2
　　1 3
　　1 4
　　1 5
　　2 5
　　2 6
　　6 9
　　7 10

Sample Output

no
　　yes 1
　　no
　　yes 1
　　no
　　yes 2
　　no
　　yes 3

HINT

1<=n<=300000 , 1<=m<=10000 , 1<=ai<=10000。

Solution

显然是一个主席树，我们建立一棵主席树然后查询是否存在个数>(l+r-1)/2的即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;

const int ONE=300005;

int n,INF,m;
int x,y,cnt;
int res_value,res_num;

struct power
{
    int root;
    int value;
    int left,right;
}Node[ONE*19];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Update(int &x,int y,int L,int R,int Q)
{
    x = ++cnt;
    Node[x].left = Node[y].left;
    Node[x].right = Node[y].right;
    Node[x].value = Node[y].value + 1;
    if(L == R) return;

    int M = (L+R)>>1;
    if(Q <= M)
        Update(Node[x].left,Node[y].left, L,M, Q);
    else
        Update(Node[x].right,Node[y].right, M+1,R, Q);
}

void Query(int x,int y,int L,int R,int Kth)
{
    if(L == R)
    {
        res_value = L;
        res_num = Node[y].value - Node[x].value;
        return;
    }

    int M = (L+R)>>1;
    int record = Node[Node[y].left].value - Node[Node[x].left].value;

    if(Kth < record)
        Query(Node[x].left,Node[y].left, L,M, Kth);
    else
        Query(Node[x].right,Node[y].right, M+1,R, Kth);
}

int main()
{
    n=get();    INF=get();
    for(int i=1;i<=n;i++)
    {
        x=get();
        Update(Node[i].root,Node[i-1].root, 1,INF, x);
    }

    m=get();
    for(int i=1;i<=m;i++)
    {
        x=get();    y=get();

        res_value = 0, res_num = 0;
        int M = (y-x+1)/2;
        Query(Node[x-1].root,Node[y].root, 1,INF, M);

        if(res_num > M)
            printf("yes %d",res_value);
        else
            printf("no");
        printf("\n");
    }
}