← 返回题目列表

AtCoder · abc405_g

G. 范围随机查询

中文机器翻译题面 查看原题

分数: 625 点

问题陈述

给你一个长度-N 序列 A = (A_1, A_2, \dots, A_N).
流程 Q 查询。
每个查询都会为您提供整数 L, R, X 并要求您解决以下问题。

让 B = (A_L, A_{L+1}, \dots, A_R) 是由以下形成的序列 L-th 通过 R第一个元素 A.
仅执行一次以下过程:

  • 首先,从 B 每个值至少为 X.
  • 然后,重新排列剩余元素 B 任意。

有多少个不同的序列 B 可以结果吗?求计数模数 998244353.

约束

  • 1 \le N \le 2.5 \times 10^5
  • 1 \le Q \le 2.5 \times 10^5
  • 1 \le A_i \le N
  • 1 \le L \le R \le N
  • 1 \le X \le N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出,其中 \mathrm{query}_i 表示 i第一个查询:

N Q
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

每个查询均按以下格式给出:

L R X

输出

输出 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。


样本输入 1

5 3
1 2 3 3 1
1 5 3
3 4 1
1 3 4

示例输出 1

3
1
6

对于第一个查询,存在三种可能的结果序列 B: (1,1,2), (1,2,1),和 (2,1,1).
对于第二个查询,有一个可能的结果序列 B:空序列 ().


示例输入 2

8 6
6 2 4 1 5 1 8 6
5 6 3
1 5 7
1 4 6
4 7 8
4 8 2
5 8 6

示例输出 2

1
120
6
3
1
2