#P50830. 「JOISC 2016 Day 3」回转寿司
「JOISC 2016 Day 3」回转寿司
题目描述
题目译自 JOISC 2016 Day3 T2 「回転寿司」
给出一个有 个点的环,环上各点有一个初始权值 。
给出 个询问,每次询问给出一个区间 和一个值 ,对于 的变动定义如下( 可能会小于 因为是环形):
for (int i = l; i <= r; i++) if(a[i] > A) swap(a[i],A);
对于每个询问,回答遍历完区间 后 的最终值。
注:我们按逆时针方向在环上编号,并规定 为从位置编号为 的点逆时针遍历至位置编号为 的点所经过点的集合。
输入格式
第一行包括两个数 与 表示环的大小和询问的个数;
之后的 行每行为一个整数,第 个为 ;
之后的 行每行有三个整数 、 、,表示如上所示。
输出格式
输出包括 行,每行包括一个数,为变动结束后 的值。
样例 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
7
9
8
7
8
6
5
第一回后, 数组长这样:,此时 ; 第二回后, 数组长这样:,此时 ; 第三回后, 数组长这样:,此时 ; 第四回后, 数组长这样:,此时 ; 第五回后, 数组长这样:,此时 ; 第六回后, 数组长这样:,此时 ; 第七回后, 数组长这样:,此时 ;
4 2
5
2
4
7
1 4 3
1 4 1
7
5
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
19
10
14
17
8
10
3
12
7
9
数据范围与提示
对于全部的数据,。
具体子任务限制及得分情况如下表:
Subtask | 限制 | 分数 |
---|---|---|
, | ||
无追加限制 |