题目描述
Coffee的世界里也是有棒棒糖卖的，Coffee买了N(1≤N≤50000)只连着的。这N只棒棒糖包裹在小塑料袋中，排成一列，相邻的两只棒棒糖的塑料袋是接起来的。为了方便，我们把棒棒糖从左到右编号为1..N。每只棒棒糖有一种口味。第i只的口味是ci(1≤ci≤50000)。两只棒棒糖i,j的口味相同，当且仅当ci=cj。Coffee对m只棒棒糖总体口味的评价比较奇怪。如果这m只棒棒糖中，有一种口味c0的数量严格大于总数的一半m/2，那么Coffee认为这m只棒棒糖主要是c0口味的。Coffee知道，这里的c0如果存在就一定是唯一的。而当c0不存在时，Coffee认为这m只棒棒糖是混合口味的。Coffee暂时舍不得吃棒棒糖，它在想一些好玩的问题。如果考虑棒棒糖序列的一个连续子序列s..t(1≤s≤t≤N)，包括棒棒糖s和t。那么这t-s+1只棒棒糖的总体口味是什么呢？Coffee有一堆这样的问题，一共M(1≤M≤50000)个。第i个问题是棒棒糖子序列si..ti的总体口味。请你帮忙解决。
输入
第1行：两个用空格隔开的整数，分别表示N,M。
第2..N+1行：每行一个整数，第i+1行表示ci。
第N+2..N+M+1行：每行两个用空格隔开的整数
第i+N+1行表示，si,ti。
输出
第1..M行：每行一个整数
第i个整数表示你对第i个问题的回答，也就是si..ti的总体口味。
如果总体口味是c0，那么回答用c0表示。
如果总体口味是混合口味，那么回答用0表示
样例输入
5 3
1
2
2
1
1
1 5
2 5
2 4
样例输出
1
0
2
题解
主席树
和 【bzoj2223】[Coci 2009]PATULJCI 做法相同。
时间复杂度 $O(n\log n)$ 。
#include <cstdio>
#define N 300001
int root[N] , lp[N << 5] , rp[N << 5] , si[N << 5] , tot;
void pushup(int x)
{
si[x] = si[lp[x]] + si[rp[x]];
}
void ins(int x , int &y , int l , int r , int p)
{
y = ++tot;
if(l == r)
{
si[y] = si[x] + 1;
return;
}
int mid = (l + r) >> 1;
if(p <= mid) rp[y] = rp[x] , ins(lp[x] , lp[y] , l , mid , p);
else lp[y] = lp[x] , ins(rp[x] , rp[y] , mid + 1 , r , p);
pushup(y);
}
int query(int x , int y , int l , int r , int p)
{
if(l == r) return l;
int mid = (l + r) >> 1;
if(si[lp[y]] - si[lp[x]] > p) return query(lp[x] , lp[y] , l , mid , p);
if(si[rp[y]] - si[rp[x]] > p) return query(rp[x] , rp[y] , mid + 1 , r , p);
return 0;
}
int main()
{
int n , lim = 50000 , m , i , x , y , t;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ )
{
scanf("%d" , &x);
ins(root[i - 1] , root[i] , 1 , lim , x);
}
while(m -- )
{
scanf("%d%d" , &x , &y);
t = query(root[x - 1] , root[y] , 1 , lim , (y - x + 1) >> 1);
if(t) printf("%d\n" , t);
else printf("0\n");
}
return 0;
}