AT_abc262_h [ABC262Ex] Max Limited Sequence

题目描述

题目大意

求满足以下条件的长度为 $N$ 的序列 $A=(A_1,A_2,\cdots A_N)$ 有多少种：

• $\mathrm{\forall }i\in [1,N],0\le A_i\le M$
• $\mathrm{\forall }i\in [1,Q],\underset{L_i\le j\le R_i}{max}{A}_j=X_i$

输入格式

第一行输入 $3$ 个正整数 $N,M,Q$

后面 $Q$ 行每行 $3$ 个正整数表示 $L_i,R_i,X_i$

$1\le N\le 2\times {10}^5$

$1\le M<998244353$

$1\le Q\le 2\times {10}^5$

$\mathrm{\forall }i\in [1,Q],1\le L_i\le R_i\le N,1\le X_i\le M$

输出格式

输出满足条件的序列数，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

3 3 2
1 2 2
2 3 3

输出 #1

5

输入输出样例 #2

输入 #2

1 1 1
1 1 1

输出 #2

1

输入输出样例 #3

输入 #3

6 40000000 3
1 4 30000000
2 6 20000000
3 5 10000000

输出 #3

135282163

题解

首先可以使用各种数据结构得出每一个下标对应的值域上界。我们对每一种值域上界所在的位置分别进行 DP。

对于 $a_i$ 的一个上界 $t_i$，我们显然只关心填的数是不饱和 $a_i<t_i$ 还是饱和 $a_i=t_i$。

对于一个询问 $[l,r]$，限制了 $[l,r]$ 范围内至少有一个位置饱和。

设 $f(i,j)$ 表示考虑到前 $i$ 个位置，最后一个饱和位置为 $j$ 的方案数。转移有三种：

1. $f(i-1,j)\to f(i,i)$，表示位置 $i$ 为饱和；
2. $f(i-1,j)\times t_i\to f(i,j)$，表示位置 $i$ 为不饱和；
3. 对于限制 $[l,i]$，将所有 $f(i,j)(j<l)$ 赋值为不饱和。

发现只需要单点赋值为全局和，全局乘，前缀清空这三种操作。可以直接维护全局和 $sum$，全局乘法标记 $tag$ 和被清空的最长前缀 $len$ 即可做到线性。

总时间复杂度 $O(n\log n)$。