题目描述
题目大意
求满足以下条件的长度为 $N$ 的序列 $A=(A_1,A_2,\cdots A_N)$ 有多少种:
- $\forall i \in[1,N],0\leq A_i\leq M$
- $\forall i \in[1,Q],\max \limits_{L_i\leq j\leq R_i}A_j=X_i$
输入格式
第一行输入 $3$ 个正整数 $N,M,Q$
后面 $Q$ 行每行 $3$ 个正整数表示 $L_i,R_i,X_i$
$1\leq N\leq 2\times 10^5$
$1\leq M<998244353$
$1\leq Q\leq 2\times 10^5$
$\forall i \in [1,Q],1\leq L_i\leq R_i\leq N,1\leq X_i\leq M$
输出格式
输出满足条件的序列数,对 $998244353$ 取模。
输入输出样例 #1
输入 #1
1 |
|
输出 #1
1 |
|
输入输出样例 #2
输入 #2
1 |
|
输出 #2
1 |
|
输入输出样例 #3
输入 #3
1 |
|
输出 #3
1 |
|
题解
首先可以使用各种数据结构得出每一个下标对应的值域上界。我们对每一种值域上界所在的位置分别进行 DP。
对于 $a_i$ 的一个上界 $t_i$,我们显然只关心填的数是不饱和 $a_i < t_i$ 还是饱和 $a_i = t_i$。
对于一个询问 $[l,r]$,限制了 $[l, r]$ 范围内至少有一个位置饱和。
设 $f(i,j)$ 表示考虑到前 $i$ 个位置,最后一个饱和位置为 $j$ 的方案数。转移有三种:
- $i$ 位置饱和时,$f(i-1,j) \rightarrow f(i,i)$;
- $i$ 位置不饱和时,$f(i-1,j) \times t_i \rightarrow f(i,j)$;
- 对于限制 $[l, i]$,将所有 $f(i,j) (j < l)$ 赋值为不饱和。
发现只需要单点赋值为全局和,全局乘,前缀清空这三种操作。可以直接维护全局和 $sum$,全局乘法标记 $tag$ 和被清空的最长前缀 $len$ 即可做到线性。
总时间复杂度 $O(n \log n)$。