AT_abc405_g [ABC405G] Range Shuffle Query

题目描述

给你一个长为 $N$ 的数列 $A=(A_1,A_2,\cdots,A_N)$，你要回答 $Q$ 个询问。

每个询问有三个参数 $(L_i,R_i,X_i)$，你需要回答：

令 $B=(A_{L_i},A_{L_i+1},\cdots,A_{R_i})$，删除 $B$ 中 $\ge X_i$ 的所有元素后，通过重新排列 $B$ 的元素可以形成多少种不同的 $B$？

答案对 $998244353$ 取模。

输入格式

第一行两个整数 $N,Q(1\le N,Q\le 2.5\times 10^5)$。
第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N(1\le A_i\le N)$。
之后 $Q$ 行，每行三个整数 $L_i,R_i,X_i(1\le L_i\le R_i\le N,1\le X_i\le N)$，表示一次询问。

输出格式

输出 $Q$ 行，每行一个整数，依次回答每个询问，答案对 $998244353$ 取模。

输入输出样例 #1

输入 #1

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

输出 #1

3
1
6

输入输出样例 #2

输入 #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

说明/提示

样例 1 解释

对于第一个询问，$B$ 的三种可能分别为：$B=(1,1,2),B=(1,2,1),B=(2,1,1)$。
对于第二个询问，$B$ 的唯一可能为空串。

By