#P18789. [KOI2026 二轮] 删除局部极小值

[KOI2026 二轮] 删除局部极小值

[KOI2026 二轮] 删除局部极小值(극솟값 제거 / Local Min)

题目描述

给定一个长度为 NN 的排列 AA。

对一个当前数列 X=[X1,…,XK]X=[X_1,\ldots,X_K],定义一次“变化”:找出所有满足

2≤i≤K−1,Xi−1>Xi<Xi+12\le i\le K-1,\qquad X_{i-1}>X_i<X_{i+1}

的元素,将它们同时删除,然后按原顺序连接剩余元素。两端的元素不会在这一轮被删除。若不存在可删除元素,变化后数列不变。

例如,[5,1,3,2,4][5,1,3,2,4] 连续变化三次的结果为

[5,1,3,2,4]→[5,3,4]→[5,4]→[5,4].[5,1,3,2,4]\to[5,3,4]\to[5,4]\to[5,4].

给定 QQ 个独立询问 (l,r,t)(l,r,t)。每个询问取出原排列中的连续段 [Al,Al+1,…,Ar][A_l,A_{l+1},\ldots,A_r],对这个段独立进行 tt 次变化,求最后剩余的元素个数。不同询问互不影响。

输入格式

第一行两个整数 N,QN,Q。

第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

接下来 QQ 行,每行三个整数 l,r,tl,r,t。

输出格式

输出 QQ 行,按输入顺序输出每个询问的剩余元素个数。

样例 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≤N,Q≤2000001\le N,Q\le200000,AA 是 1,…,N1,\ldots,N 的排列。每个询问满足 1≤l≤r≤N1\le l\le r\le N、1≤t≤N1\le t\le N。

子任务 分值 附加限制
1 6 N≤5000N\le5000,所有询问 l=1,r=Nl=1,r=N
2 11 所有询问 l=1,r=Nl=1,r=N
3 6 所有询问 t=1t=1
4 12 所有询问 t=Nt=N
5 7 存在 pp,使 A1>⋯>Ap<Ap+1<⋯<ANA_1>\cdots>A_p<A_{p+1}<\cdots<A_N,两侧允许为空
6 26 原排列整体变化 2020 次后已经稳定
7 32 无附加限制

满分 100 分。时限 2 秒,内存 1024 MiB。