P3084 [USACO13OPEN] Photo G

2huk · 2024-08-09 20:49:01 · 题解

题意

求有多少个长度为 n 的 01 序列，满足 [l_1,r_1],[l_2,r_2],\dots,[l_m,r_m] 这些区间中都恰有一个 1。

做法

令 f(i) 表示前 i 个的答案，且第 i 个是 1。考虑从哪些 j 转移而来。

“恰有 1 个”转化成“至少 1 个”且“最多 1 个”。

至少一个，说明不存在一个区间 [l, r] 使得 [l, r] \subseteq [j+1, i-1]。因为如果存在那么 [l, r] 中 1 的出现次数为 0。

不存在 [l, r] \subseteq [j+1, i-1] 等价于对于任意 r \le i - 1，都满足 l \le j。所以可以维护满足这个条件的 l 的最大值。

最多一个同理。对于任意 r \ge i，都满足 l \ge j。维护满足这个条件的 l 的最小值。

那么能转移过来的 j 是一段区间。线段树即可。

观察到这个 j 的区间的左右端点是分别递增的。所以单调队列也可以。但是代码不太好写。

复杂度线性或带个 \log。