#2736. 「JOISC 2016 Day 3」回转寿司

内存限制:256 MiB 时间限制:9000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: styx

题目描述

题目译自 JOISC 2016 Day3 T2 「回転寿司

给出一个有 N 个点的环,环上各点有一个初始权值 a_i

给出 Q 个询问,每次询问给出一个区间 [l,r] 和一个值 A ,对于 A 的变动定义如下( r 可能会小于 l 因为是环形):

for (int i = l; i <= r; i++) if(a[i] > A) swap(a[i],A);

对于每个询问,回答遍历完区间 [l,r] A 的最终值。

注:我们按逆时针方向在环上编号,并规定 [l,r] 为从位置编号为 l 的点逆时针遍历至位置编号为 r 的点所经过点的集合。

输入格式

第一行包括两个数 N Q 表示环的大小和询问的个数;
之后的 N 行每行为一个整数,第 i 个为 a_i
之后的 Q 行每行有三个整数 l_i r_i A_i ,表示如上所示。

输出格式

输出包括 Q 行,每行包括一个数,为变动结束后 A_i 的值。

样例

样例输入 1

6 7
8
6
7
4
5
9
2 4 5
4 1 4
6 2 7
1 5 2
3 4 8
4 3 1
3 1 3

样例输出 1

7
9
8
7
8
6
5

样例解释 1

第一回后, a 数组长这样: 8, 5, 6, 4, 5, 9 ,此时 A=7
第二回后, a 数组长这样: 8, 5, 6, 4, 4, 5 ,此时 A=9
第三回后, a 数组长这样: 7, 5, 6, 4, 4, 5 ,此时 A=8
第四回后, a 数组长这样: 2, 5, 6, 4, 4, 5 ,此时 A=7
第五回后, a 数组长这样: 2, 5, 6, 4, 4, 5 ,此时 A=8
第六回后, a 数组长这样: 2, 5, 5, 1, 4, 4 ,此时 A=6
第七回后, a 数组长这样: 2, 5, 3, 1, 4, 4 ,此时 A=5

样例输入 2

4 2
5
2
4
7
1 4 3
1 4 1

样例输出 2

7
5

样例输入 3

10 10
19
5
8
17
14
3
9
10
7
6
1 8 4
7 3 2
5 9 10
4 8 3
10 3 6
8 7 4
6 6 3
2 9 12
6 3 7
9 6 3

样例输出 3

19
10
14
17
8
10
3
12
7
9

数据范围与提示

对于全部的数据, 1 \leq N \leq 4\times 10^{5} ,1 \leq Q \leq 25000 ,1 \leq a_i \leq 10^{9},1 \leq l,r \leq N,1 \leq A \leq 10^{9}

具体子任务限制及得分情况如下表:

Subtask 限制 分数
1 1 \leq N \leq 2000 , 1 \leq Q \leq 2000 5
2 l=1,r=N 15
3 无追加限制 80