AT_arc182_a.[ARC182A] Chmax Rush!
普及+/提高
通过率：0%
AC君温馨提醒
该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
有一个长度为 N 的整数序列 S。初始时，S 的所有元素均为 0。
另外，给定长度为 Q 的整数序列 P=(P1,P2,…,PQ) 和 V=(V1,V2,…,VQ)。
すぬけ君想要对数列 S 顺次进行 Q 次操作。第 i 次操作如下：
- 可以进行以下两种操作之一。
- 将 S1,S2,…,SPi 全部替换为 Vi。但如果在这次操作前，S1,S2,…,SPi 中存在严格大于 Vi 的元素，すぬけ君会哭出来。
- 将 SPi,SPi+1,…,SN 全部替换为 Vi。但如果在这次操作前，SPi,SPi+1,…,SN 中存在严格大于 Vi 的元素，すぬけ君会哭出来。
请计算，能够使すぬけ君不哭地完成 Q 次操作的操作序列有多少种，将答案对 998244353 取模。
这里，若存在某个 1≤i≤Q，使得在第 i 次操作中选择的操作不同，则认为两个操作序列是不同的。
输入格式
输入按以下格式从标准输入读入。
N Q P1 V1 P2 V2 ⋮ PQ VQ
输出格式
请输出一个整数作为答案。
输入输出样例
输入#1
8 3 1 8 8 1 2 1
输出#1
1
输入#2
8 3 8 1 1 8 1 2
输出#2
0
输入#3
241 82 190 3207371 229 3639088 61 4428925 84 17258698 34 42692503 207 59753183 180 67198566 78 99285033 60 102449991 234 122146510 111 126959145 141 152331579 78 159855439 11 169658471 22 189991287 37 204602946 73 209329065 72 215363269 152 236450854 175 237822921 22 261431608 144 252550201 54 268889550 238 276997357 69 313065279 226 330144323 6 335788783 126 345410019 220 348318997 166 365778763 142 382251905 200 406191336 234 392702679 83 409660987 183 410908761 142 445707116 205 470279207 230 486436406 156 494269002 113 495687706 200 500005738 162 505246499 201 548652987 86 449551554 62 459527873 32 574001635 230 601073337 175 610244315 174 613857555 181 637452273 158 637866397 148 648101378 172 646898076 144 682578257 239 703460335 192 713255331 28 727075136 196 730768166 111 751850547 90 762445737 204 762552166 72 773170159 240 803415865 32 798873367 195 814999380 72 842641864 125 851815348 116 858041919 200 869948671 195 873324903 5 877767414 105 877710280 150 877719360 9 884707717 230 880263190 88 967344715 49 977643789 167 979463984 70 981400941 114 991068035 94 991951735 141 995762200
输出#3
682155965
说明/提示
数据范围
- 2≤N≤5000
- 1≤Q≤5000
- 1≤Pi≤N
- 1≤Vi≤109
- 输入均为整数
样例解释 1
如下操作可以使すぬけ君不哭地完成 3 次操作：
- 将 S1 替换为 8。
- 将 S8 替换为 1。
- 将 S2,S3,…,S8 替换为 1。
除此之外，没有其他满足条件的操作序列，所以答案为 1。例如，如果第 1 次操作选择将 S1,S2,…,S8 替换为 8，那么第 2 次操作无论选择哪种方式，すぬけ君都会哭出来。
样例解释 2
无论前两次操作如何进行，在第 3 次操作时すぬけ君都会哭出来。
样例解释 3
不要忘记将答案对 998244353 取模。
由 ChatGPT 4.1 翻译
输入解题思路，AI测评打分。不知道怎么写?