#XMOJ12269. 多人涂色比赛
多人涂色比赛
说明
时间限制:3 Sec
内存限制:256 MB
输入文件:color.in 输出文件:color.out
玩家分为 A、B、C、D、E 五支队伍,用代表各自队伍的颜色对同一个数组进行涂色争夺。
最终得分等于被本队颜色涂过的元素数量加上后文所述奖励分,得分最高的队伍获胜。
规则
1. 给定长度为 $N$ 的数组,初始全部未被涂色。也就是说,所有位置上各个颜色的厚度都是 $0$。
2. 五支队伍可以选择数组区间 $[l,r]$,用自己队伍的颜色进行涂色:
- 如果该位置完全没有被涂过:涂上本队颜色,本队颜色厚度变为 $1$。
- 如果该位置已经是本队颜色:本队颜色厚度 $+1$。
- 如果该位置是别的队伍颜色:被本次颜色覆盖,其他队伍厚度清零,本队厚度置为 $1$。
3. 游戏会不定期触发奖励机会。
- 奖励机会给出区间 $[l,r]$,设区间 $[l,r]$ 内队伍X的颜色厚度总和为 $X_{lr}$($X=A,B,C,D,E$)。
- 如果有且仅有一支队伍的 $X_{lr}$ 是最大值,则给这支队伍加上 $\max(A_{lr},B_{lr},C_{lr},D_{lr},E_{lr})$ 的奖励分。
- 如果最大值存在并列,则任何队伍都得不到奖励分。
4. 游戏结束时,每支队伍的总得分 = 整个数组 $[0,N-1]$ 上本队颜色厚度总和 + 累计得到的奖励分。
游戏已经结束,只需要计算最终分数。按时间顺序给出所有队伍操作和奖励机会,请输出五支队伍的最终得分。
输入格式
第一行一个整数 $N$。
第二行一个整数 $Q$。
接下来 $Q$ 行,每行三个整数 $x_k,l_k,r_k$。
- $x_k=0$:区间 $[l_k,r_k]$ 的奖励机会
- $x_k=1$:队伍 A 对区间 $[l_k,r_k]$ 涂色
- $x_k=2$:队伍 B 对区间 $[l_k,r_k]$ 涂色
- $x_k=3$:队伍 C 对区间 $[l_k,r_k]$ 涂色
- $x_k=4$:队伍 D 对区间 $[l_k,r_k]$ 涂色
- $x_k=5$:队伍 E 对区间 $[l_k,r_k]$ 涂色
输出格式
输出队伍 A、B、C、D、E 的得分,每个分数对 $10^{18}+9$ 取模,用空格隔开。
样例
样例 1
5
2
1 0 3
2 2 4
2 3 0 0 0
样例 2
5
3
1 0 4
2 1 3
0 4 4
3 3 0 0 0
样例 3
6
6
1 1 2
2 4 5
0 2 4
2 0 3
1 1 5
0 0 5
10 1 0 0 0
数据范围
对于 100% 的数据,$1 \leq N \leq 10^{13}$,$0 \leq Q \leq 1.5\times 10^5$,$0 \leq x_k \leq 5$,$0 \leq l_k \leq r_k \lt N$。
相关
在下列比赛中: