P14558 [ROI 2013 Day2] 大规模预测

在学校信息学俱乐部主席选举中，有 $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$）。

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

此题的最终解答检查使用 $50$ 个测试。测试独立评分。每个测试分值为 $2$ 分。测试中 $N$ 和 $K$ 的值见下表。 | **测试** | $\mathbf{N}$ | $\mathbf{K}$ | **测试** | $\mathbf{N}$ | $\mathbf{K}$ | **测试** | $\mathbf{N}$ | $\mathbf{K}$ | |:--------:|:------------:|:------------:|:--------:|:------------:|:------------:|:--------:|:------------:|:------------:| | $1.$ | $2$ | $2$ | $18.$ | $2000$ | $20$ | $35.$ | $90000$ | $1000$ | | $2.$ | $3$ | $1$ | $19.$ | $3000$ | $2000$ | $36.$ | $100000$ | $5000$ | | $3.$ | $5$ | $5$ | $20.$ | $5000$ | $2000$ | $37.$ | $125000$ | $1$ | | $4.$ | $10$ | $10$ | $21.$ | $7500$ | $200$ | $38.$ | $150000$ | $12000$ | | $5.$ | $20$ | $2$ | $22.$ | $10000$ | $10000$ | $39.$ | $150000$ | $18$ | | $6.$ | $30$ | $3$ | $23.$ | $15000$ | $1500$ | $40.$ | $200000$ | $42000$ | | $7.$ | $50$ | $20$ | $24.$ | $20000$ | $10$ | $41.$ | $250000$ | $26000$ | | $8.$ | $75$ | $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$ | $10000$ | $46.$ | $500000$ | $2$ | | $13.$ | $400$ | $100$ | $30.$ | $50000$ | $10000$ | $47.$ | $500000$ | $102000$ | | $14.$ | $500$ | $2$ | $31.$ | $55000$ | $13000$ | $48.$ | $500000$ | $102000$ | | $15.$ | $300$ | $200$ | $32.$ | $60000$ | $174$ | $49.$ | $500000$ | $102000$ | | $16.$ | $1000$ | $2000$ | $33.$ | $70000$ | $10000$ | $50.$ | $500000$ | $501$ | | $17.$ | $1500$ | $100$ | $34.$ | $80000$ | $1000$ | | | | --- 翻译由 DeepSeek V3 完成