PDF《IOI 2018 中国国家集训队集中培训》

1 ? A 中的正整 数音高.因此

1 ≤ hi ≤ A. 在写歌之前,IA 需要确定下这首歌的结构,于是她写下了 Q 条限制,其中第 i 条为:编号在 li 到ri 之间的音符的最高音高为 mi.在确定了结构之后,她就可以开始写 歌了.不过她还是想知道,一共有多少种可能的歌曲满足她的所有限制?她听说你还有

9 个月就要去 IOI 了,于是希望你帮她计算一下这个值. 【输入格式】 从文件 rmq.in 中读入数据. 输入的第一行包含一个整数 T(T ≤ 20),代表测试数据的组数. 每组数据的第一行包含三个正整数 n, Q, A.接下来 Q 行,每行三个整数 li, ri, mi, 表示一条限制.保证

1 ≤ li ≤ ri ≤ n,1 ≤ mi ≤ A. 【输出格式】 输出到文件 rmq.out 中. 输出文件只有一行, 表示可能的歌曲数目. 这个数可能很大, 请将答案模

998244353 输出. 【样例

1 输入】

1 3

2 3

1 2

3 2

3 2 【样例

1 输出】

3 【样例

1 解释】 以下是三种可能的歌曲:(3, 1, 2), (3, 2, 1), (3, 2, 2). 第9页共10 页IOI

2018 中国国家集训队集中培训 第四试 某位歌姬的故事(rmq) 【样例

2 输入】

2 4

2 4

1 2

3 2

3 4

7 3

74 3

6 56

2 5

56 3

7 70 【样例

2 输出】

20 160326468 【子任务】 测试点编号 n Q A mi 分数

1 ≤

7 ≤

7 ≤

7 ≤ A

5 2 ≤

10 ≤

500 ≤

9 *

108 ≤ A

10 3 ≤

500 ≤

10 ≤

9 *

108 ≤ A

8 4 ≤

500 ≤

500 =

2 =

2 12

5 ≤

9 *

108 ≤

500 =

2 =

2 18

6 ≤

500 ≤

500 ≤

9 *

108 ≤ A

28 7 ≤

9 *

108 ≤

500 ≤

9 *

108 ≤ A

19 第10 页共10 页 ........