题目描述
样例输入
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。
题解
bzoj格式错了。。。
主席树。
对于每个询问，判断它能在左边出现还是能在右边出现，都不能则不存在，能则继续寻找。略水。
不需要离散化。
1 #include <cstdio> 2 #define N 300001 3 int root[N] , lp[N << 5] , rp[N << 5] , si[N << 5] , tot; 4 void pushup(int x) 5 { 6 si[x] = si[lp[x]] + si[rp[x]]; 7 } 8 void ins(int x , int &y , int l , int r , int p) 9 { 10 y = ++tot; 11 if(l == r) 12 { 13 si[y] = si[x] + 1; 14 return; 15 } 16 int mid = (l + r) >> 1; 17 if(p <= mid) rp[y] = rp[x] , ins(lp[x] , lp[y] , l , mid , p); 18 else lp[y] = lp[x] , ins(rp[x] , rp[y] , mid + 1 , r , p); 19 pushup(y); 20 } 21 int query(int x , int y , int l , int r , int p) 22 { 23 if(l == r) return l; 24 int mid = (l + r) >> 1; 25 if(si[lp[y]] - si[lp[x]] > p) return query(lp[x] , lp[y] , l , mid , p); 26 if(si[rp[y]] - si[rp[x]] > p) return query(rp[x] , rp[y] , mid + 1 , r , p); 27 return 0; 28 } 29 int main() 30 { 31 int n , lim , m , i , x , y , t; 32 scanf("%d%d" , &n , &lim); 33 for(i = 1 ; i <= n ; i ++ ) 34 { 35 scanf("%d" , &x); 36 ins(root[i - 1] , root[i] , 1 , lim , x); 37 } 38 scanf("%d" , &m); 39 while(m -- ) 40 { 41 scanf("%d%d" , &x , &y); 42 t = query(root[x - 1] , root[y] , 1 , lim , (y - x + 1) >> 1); 43 if(t) printf("yes %d\n" , t); 44 else printf("no\n"); 45 } 46 return 0; 47 }
原文：http://www.cnblogs.com/GXZlegend/p/6292609.html