[ROI 2013 Day2] 大规模预测

ID: 14220

远端评测题

1000ms

256MiB

难度: 8

上传者:

标签>

2013

ROI（俄罗斯）

题目描述

在学校信息学俱乐部主席选举中，有 $K$ 名候选人和 $N$ 名选民。候选人编号从 $1$ 到 $K$ ，选民编号从 $1$ 到 $N$ 。

根据投票结果生成一个列表，该列表的第 $i$ 个元素等于第 $i$ 名选民投票支持的候选人编号。为列表的每个区间指派一名观察员，统计该区间内的票数。因此，选举中共有 $N(N + 1) / 2$ 名观察员工作。

如果观察员发现在其负责的区间内有候选人获得超过半数的票数，他会在社交网络上发布预测，认为该候选人将在选举中获胜。

需要编写一个程序，根据投票列表确定观察员发布的预测数量。

输入文件的第一行包含两个数字 $N$ 和 $K$ （ $1 \le N \le 500,000$ ， $1 \le K \le 500,000$ ）。第二行包含 $N$ 个数字 $V_1, V_2, \ldots, V_N$ ——选民的投票列表（ $1 \le V_i \le K$ ）。

输出文件应包含一个数字——预测的数量。

5 2
1 2 1 2 1

3 7
5 2 6

此题的最终解答检查使用 $50$ 个测试。测试独立评分。每个测试分值为 $2$ 分。测试中 $N$ 和 $K$ 的值见下表。

测试	$\mathbf{N}$	$\mathbf{K}$	测试	$\mathbf{N}$	$\mathbf{K}$	测试	$\mathbf{N}$	$\mathbf{K}$
$1.$	$2$		$18.$	$2000$	$20$	$35.$	$90000$	$1000$
$2.$	$3$	$1$	$19.$	$3000$	$2000$	$36.$	$100000$	$5000$
$3.$	$5$		$20.$	$5000$	$2000$	$37.$	$125000$	$1$
$4.$	$10$		$21.$	$7500$	$200$	$38.$	$150000$	$12000$
$5.$	$20$	$2$	$22.$	$10000$		$39.$	$150000$	$18$
$6.$	$30$	$3$	$23.$	$15000$	$1500$	$40.$	$200000$	$42000$
$7.$	$50$	$20$	$24.$	$20000$	$10$	$41.$	$250000$	$26000$
$8.$	$75$		$25.$	$25000$	$100$	$42.$	$300000$	$10000$
$9.$	$100$	$2000$	$26.$	$30000$	$15$	$43.$	$350000$	$102000$
$10.$	$150$	$30$	$27.$	$35000$	$35$	$44.$	$400000$	$12000$
$11.$	$200$	$50$	$28.$	$40000$	$10000$	$45.$	$450000$	$5000$
$12.$	$300$	$10$	$29.$	$45000$		$46.$	$500000$	$2$
$13.$	$400$	$100$	$30.$	$50000$		$47.$		$102000$
$14.$	$500$	$2$	$31.$	$55000$	$13000$	$48.$
$15.$	$300$	$200$	$32.$	$60000$	$174$	$49.$
$16.$	$1000$	$2000$	$33.$	$70000$	$10000$	$50.$		$501$
$17.$	$1500$	$100$	$34.$	$80000$	$1000$

翻译由 DeepSeek V3 完成