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