题目描述
样例输入
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
样例输出
no
yes 1
no
yes 1
no
yes 2
no
yes 3
样例描述
第一行输入n和lim,为序列数的个数和数的范围(1≤a[i]≤lim)
第二行输入n个数。
第三行输入m,为询问个数。
以下m行输入询问,如题。
对于每个询问,如果存在,输出yes和这个数,否则输出no。
题解:
主席树.
因为个数要大于\((r - l + 1)/2\)所以我们应该查询左子树相减的个数是否大于这个数,右子树相减是否大于这个数.(这个是利用左右子树的个数和主席树的性质来解)
ps:貌似我没有好好利用lim,还是离散化了,_huaji_
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxN = 3e5 + 7;
int root[maxN],a[maxN],s[maxN],cnt;
struct Node {
int lc,rc;
int ans;
} tree[maxN * 20];
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
void add(int &now,int last,int l,int r,int p) {
now = ++ cnt;
tree[now].ans = tree[last].ans + 1;
tree[now].lc = tree[last].lc;
tree[now].rc = tree[last].rc;
if(l == r)return;
int mid = (l + r) >> 1;
if(mid >= p) add(tree[now].lc,tree[last].lc,l,mid,p);
else add(tree[now].rc,tree[last].rc,mid + 1,r,p);
}
int query(int L,int R,int l,int r,int p) {
if(l == r) return l;
int mid = (l + r) >> 1;
if(tree[tree[R].lc].ans - tree[tree[L].lc].ans > p) return query(tree[L].lc,tree[R].lc,l,mid,p);
if(tree[tree[R].rc].ans - tree[tree[L].rc].ans > p) return query(tree[L].rc,tree[R].rc,mid + 1,r,p);
return 0;
}
int main() {
freopen("bzoj2223.in","r",stdin);
freopen("bzoj2223.out","w",stdout);
int n,m,lim;
n = read();lim = read();
for(int i = 1; i <= n; ++ i)
s[i] = a[i] = read();
sort(s + 1,s + n + 1);
for(int i = 1; i <= n; ++ i) {
int p = lower_bound(s + 1,s + n + 1,a[i]) - s;
add(root[i],root[i - 1],1,n,p);
}
int l,r;
m = read();
while(m --) {
l = read();
r = read();
int p = query(root[l - 1],root[r],1,n,(r - l + 1) >> 1);
p != 0 ? printf("yes %d\n" ,s[p]) : printf("no\n") ;
}
return 0;
}