LibreOJ

2736 「JOISC 2016 Day 3」回转寿司

内存限制：256 MB 时间限制：9000 ms

题目描述

题目译自 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

第一回后，$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

样例 3

数据范围与提示

对于全部的数据，$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$

样例

样例输入 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

样例输入 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