#P18789. [KOI2026 二轮] 删除局部极小值
[KOI2026 二轮] 删除局部极小值
[KOI2026 二轮] 删除局部极小值(극솟값 제거 / Local Min)
题目描述
给定一个长度为 的排列 。
对一个当前数列 ,定义一次“变化”:找出所有满足
的元素,将它们同时删除,然后按原顺序连接剩余元素。两端的元素不会在这一轮被删除。若不存在可删除元素,变化后数列不变。
例如, 连续变化三次的结果为
给定 个独立询问 。每个询问取出原排列中的连续段 ,对这个段独立进行 次变化,求最后剩余的元素个数。不同询问互不影响。
输入格式
第一行两个整数 。
第二行 个整数 。
接下来 行,每行三个整数 。
输出格式
输出 行,按输入顺序输出每个询问的剩余元素个数。
样例 1
5 5
5 1 3 2 4
1 5 1
1 5 2
1 4 1
2 5 1
1 5 5
3
2
3
3
2
样例 2
15 7
14 5 2 7 11 13 3 12 9 4 10 8 1 6 15
1 15 1
1 15 2
1 15 3
1 15 4
1 15 5
1 15 6
1 15 7
11
8
6
4
3
2
2
样例 3
10 10
9 6 4 1 8 2 3 5 7 10
1 10 1
1 10 2
1 10 5
1 9 3
2 10 2
2 10 4
3 8 1
3 8 2
1 5 4
4 8 3
8
6
2
3
5
3
4
3
2
3
数据范围与子任务
所有输入均为整数。, 是 的排列。每个询问满足 、。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 6 | ,所有询问 |
| 2 | 11 | 所有询问 |
| 3 | 6 | 所有询问 |
| 4 | 12 | 所有询问 |
| 5 | 7 | 存在 ,使 ,两侧允许为空 |
| 6 | 26 | 原排列整体变化 次后已经稳定 |
| 7 | 32 | 无附加限制 |
满分 100 分。时限 2 秒,内存 1024 MiB。