题目描述
给定长度为 n 的序列 S,其中每个元素都是 [0,m) 内的整数。
定义 count(s,i) 为 S 在位置 min(s,i) 到 max(s,i) 之间的连续片段中,本质不同的非空子序列数量。子序列通过删除任意若干个元素得到,保留其余元素的相对顺序。
每次询问给出 s,l,r,求下式对 998244353 取模的结果。
i=l∑rcount(s,i)
输入格式
第一行三个整数 n,m,q。第二行 n 个整数,表示序列 S。
接下来 q 行,每行三个整数 s,l,r,表示一次询问。
输出格式
输出 q 行,每行一个整数,表示对应询问的答案。
样例
5 3 6
0 2 1 2 1
3 4 5
5 1 1
3 3 4
5 2 3
1 4 4
1 1 5
9
23
4
17
13
47
数据范围
n,q≤2×105,m≤2000,max(nm,qm)≤107,1≤s≤n,1≤l≤r≤n。
| 原赛子任务 |
特殊限制 |
原赛分值 |
| 1 |
n,m,q≤1000 |
1 |
| 2 |
m≤5 |
29 |
| 3 |
l=r |
30 |
| 4 |
无 |
40 |
原 PDF 题面