[BZOJ3524][Poi2014]Couriers

[BZOJ3524][Poi2014]Couriers

试题描述

给一个长度为n的序列a。1≤a[i]≤n。
m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。

输入

第一行两个数n，m。
第二行n个数，a[i]。
接下来m行，每行两个数l,r，表示询问[l,r]这个区间。

输出

m行，每行对应一个答案。

输入示例

7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6

输出示例

1
0
3
0
4

数据规模及约定

n,m≤500000

题解

在区间 [l, r] 内，如果一个数出现了多于 (r - l + 1) 次，那么对于任意区间 [x, y] ∈ [l, r] 且 [x, y] 不包含这个数，都有 [x, y] 所包含的所有数的个数小于 (r - l + 1)。

利用这个性质，就可以二分找到这个数了。主席树裸题。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;

const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
	if(Head == Tail) {
		int l = fread(buffer, 1, BufferSize, stdin);
		Tail = (Head = buffer) + l;
	}
	return *Head++;
}
int read() {
	int x = 0, f = 1; char c = Getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
	return x * f;
}

#define maxn 500010
#define maxnode 10000010

int n, ToT, rt[maxn], sumv[maxnode], lc[maxnode], rc[maxnode];
void update(int& y, int x, int l, int r, int p) {
	sumv[y = ++ToT] = sumv[x] + 1;
	if(l == r) return ;
	int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x];
	if(p <= mid) update(lc[y], lc[x], l, mid, p);
	else update(rc[y], rc[x], mid + 1, r, p);
	return ;
}

int main() {
	n = read(); int q = read();
	for(int i = 1; i <= n; i++) update(rt[i], rt[i-1], 1, n, read());
	
	while(q--) {
		int ql = read(), qr = read(), lrt = rt[ql-1], rrt = rt[qr], l = 1, r = n;
		while(l < r) {
			int mid = l + r >> 1;
			if(sumv[lc[rrt]] - sumv[lc[lrt]] <= (qr - ql + 1 >> 1))
				l = mid + 1, lrt = rc[lrt], rrt = rc[rrt];
			else r = mid, lrt = lc[lrt], rrt = lc[rrt];
		}
		if(sumv[rrt] - sumv[lrt] > (qr - ql + 1 >> 1)) printf("%d
", l);
		else puts("0");
	}
	
	return 0;
}