P14140 「SFMOI Round II」Strange Alice Game
题目背景
TL: 1s -> 1.5s
---
你的抓取确实很强，但是我可以 z+x。
题目描述
诺艾儿是出身于正统精灵的炼金术师的家系中分出的柯涅尔家族的后裔，是精灵、人类和兽人的混血，面对危险的世界，她需要提升自己能力，具体来说，她需要试炼。
试炼的地方可以简化成 $n$ 个区域，每个区域有一个危险等级为 $a_i$ 的魔族，**$a_i$ 各不相同**。
诺艾儿会进行 $q$ 次试炼，每次试炼最多攻击 $k$ 个魔族，一次试炼诺艾儿会从 $l$ 出发，前往 $r$ 并传送回家。
诺艾儿会依次遇到 $l$ 到 $r$ 位置的魔族，每遇到一个魔族 $(i,a_i)$，诺艾儿可以选择：
1. 不打它。
2. 打它，并且满足：
- 已经打的魔族数目不足 $k$。
- 对于任意魔族 $j$，如果 $l\le j
输入格式
第一行三个正整数 $n,k,q$ 表示试炼之地可划分成的区域数目，一次试炼最多攻击多少个魔族，一共进行多少次试炼。
第二行 $n$ 个正整数，第 $i$ 个正整数 $a_i\ (1\le a_i \le n)$ 表示在 $i$ 位置魔族的危险度。
接下来 $q$ 行，每行两个正整数 $l,r\ (1\le l\le r \le n)$，表示一次试炼是从 $l$ 到 $r$ 进行。
输出格式
输出 $q$ 行，第 $i$ 行表示对于第 $i$ 次试炼的答案。
说明/提示
| 子任务编号 | $n\le $ | $q\le $ | 特殊性质 | 分值 | 时间限制 |
| :--------------: | :---------: | :---------: | :----------------------: | :--: | -------- |
| $0$ | $ 4000$ | $4000$ | 无 | $5$ | ~~1s~~ 1.5s |
| $1$ | $10^5$ | $10^5$ | $k\le 10$，$a_i$ 随机生成 | $25$ | ^ |
| $2$ | $10^5$ | $10^5$ | 无 | $20$ | ^ |
| $3$ | $10^6$ | $10^6$ | 无 | $50$ | ^ |
对于 $100\%$ 的数据，满足 $1\le k\le n\le 10^6,1\le q\le 10^6,1\le a_i \le n$；
其中 $a_i$ 随机生成的方式为 $a$ 从所有排列中随机选择一个。