#P6872. 十里山路

    ID: 6703 传统题 1000ms 888MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-计数 DP转移矩阵转移矩阵乘积矩阵求逆一维前缀和增量维护离线查询对称性分析

十里山路

题目描述

给定长度为 nn 的序列 SS,其中每个元素都是 [0,m)[0,m) 内的整数。

定义 count⁡(s,i)\operatorname{count}(s,i) 为 SS 在位置 min⁡(s,i)\min(s,i) 到 max⁡(s,i)\max(s,i) 之间的连续片段中,本质不同的非空子序列数量。子序列通过删除任意若干个元素得到,保留其余元素的相对顺序。

每次询问给出 s,l,rs,l,r,求下式对 998244353998244353 取模的结果。

∑i=lrcount⁡(s,i)\sum_{i=l}^{r}\operatorname{count}(s,i)

输入格式

第一行三个整数 n,m,qn,m,q。第二行 nn 个整数,表示序列 SS。

接下来 qq 行,每行三个整数 s,l,rs,l,r,表示一次询问。

输出格式

输出 qq 行,每行一个整数,表示对应询问的答案。

样例

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×105n,q\le2\times10^5,m≤2000m\le2000,max⁡(nm,qm)≤107\max(nm,qm)\le10^7,1≤s≤n1\le s\le n,1≤l≤r≤n1\le l\le r\le n。

原赛子任务 特殊限制 原赛分值
1 n,m,q≤1000n,m,q\le1000 1
2 m≤5m\le5 29
3 l=rl=r 30
4 无 40

原 PDF 题面