Rockdu's Blog

题目描述

Byteasar works for the BAJ company, which sells computer games.

The BAJ company cooperates with many courier companies that deliver the games sold by the BAJ company to its customers.

Byteasar is inspecting the cooperation of the BAJ company with the couriers.

He has a log of successive packages with the courier company that made the delivery specified for each package.

He wants to make sure that no courier company had an unfair advantage over the others.

If a given courier company delivered more than half of all packages sent in some period of time, we say that it dominated in that period.

Byteasar wants to find out which courier companies dominated in certain periods of time, if any.

Help Byteasar out!

Write a program that determines a dominating courier company or that there was none.

给一个数列，每次询问一个区间内有没有一个数出现次数超过一半

输入输出格式

输入格式：

The first line of the standard input contains two integers,  and  (), separated by a single space, that are the number of packages shipped by the BAJ company and the number of time periods for which the dominating courier is to be determined, respectively.

The courier companies are numbered from  to (at most) .

The second line of input contains  integers,  (), separated by single spaces;  is the number of the courier company that delivered the -th package (in shipment chronology).

The  lines that follow specify the time period queries, one per line.

Each query is specified by two integers,  and  (), separated by a single space.

These mean that the courier company dominating in the period between the shipments of the -th and the -th package, including those, is to be determined.

In tests worth  of total score, the condition  holds, and in tests worth  of total score .

输出格式：

The answers to successive queries should be printed to the standard output, one per line.

(Thus a total of  lines should be printed.) Each line should hold a single integer: the number of the courier company that dominated in the corresponding time period, or  if there was no such company.

输入输出样例

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

1
0
3
0
4

说明

给一个数列，每次询问一个区间内有没有一个数出现次数超过一半

赛前打板子。这道题询问一个区间内有没有一个数出现次数超过一半，那么我们直接在序列上构造主席树。对于每一个询问提取出区间的权值线段树进行查询——向下递归操作：如果左权值区间的数的个数大于一半我们就查询左子树，如果右权值区间的数的个数大于一半我们同样进入右子树，如果都不满足反回-1即可。(考虑到线段树是二分的结构，左右个数相同的情况也是有的。不可以用else)。这样我们就完成了上述操作。

#include<cstdio>
using namespace std;
const int maxn = 5e5 + 5;

int n, m, a, b;
namespace PST {
	const int L = 0, R = 1;
	int root[maxn], cnt;
	struct node {int sum, ch[2];}tree[maxn * 40];
	void push_up(int rt) {
		tree[rt].sum = tree[tree[rt].ch[L]].sum + tree[tree[rt].ch[R]].sum;
	}
	void insert(int x, int tl, int tr, int & rt) {
		tree[++cnt] = tree[rt], rt = cnt;
		if(tl == tr) {++tree[rt].sum; return ;}
		int mid = tl + tr >> 1;
		if(x <= mid) insert(x, tl, mid, tree[rt].ch[L]);
		else insert(x, mid + 1, tr, tree[rt].ch[R]);
		push_up(rt);
	}
	int query(int sum, int tl, int tr, int lrt, int rrt) {
		if(tl == tr) return tl;
		int mid = tl + tr >> 1, llc = tree[lrt].ch[L], rlc = tree[rrt].ch[L];
		int lrc = tree[lrt].ch[R], rrc = tree[rrt].ch[R];
		if(tree[rlc].sum - tree[llc].sum > sum) return query(sum, tl, mid, llc, rlc);
		if(tree[rrc].sum - tree[lrc].sum > sum) return query(sum, mid + 1, tr, lrc, rrc);
		return 0;
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for(register int i = 1; i <= n; ++i) 
		scanf("%d", &a), PST::insert(a, 1, n, PST::root[i] = PST::root[i - 1]);
	for(register int i = 1; i <= m; ++i) {
		scanf("%d%d", &a, &b);
		printf("%d\n", PST::query((b - a + 1) / 2, 1, n, PST::root[a - 1], PST::root[b]));
	}
	return 0;
}