CF1327F AND Segments
这题好像有点简单。
肯定先拆位，限制转化为两种：
- 强制 $[l_i,r_i] $全为1
- 强制 $[l_i,r_i] $不全为1
对于第一种限制，这时候 \([l_i,r_i]\) 已经确定了，所以可以直接差分一下直接把这一部分的 \(a\) 求出来，剩下的 \(a\) 只需考虑第二种限制。
维护 \(L_i\) 表示满足最小的位置 \(p\) 使得 \([p,i)\) 可以全部为 \(1\)，设 \(f_i\) 表示最后一个填的位置是 \(i\)，已经满足了右端点在 \([1, i]\) 内的限制的方案数。那么转移是很简单的。
\[f_i = \sum_{L_{i - 1} < k < i} f_k \]这个直接用前缀和维护一下就可以了。
详情
#include <cstdio>
#include <iostream>
#define LL long long
using namespace std;
template <typename T>
inline void read(T &x) {
x = 0; int f = 0; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
if(f) x = ~x + 1;
}
const int N = 5e5 + 10;
const int P = 998244353;
int n, m, k;
int l[N], r[N], v[N], pos[N];
int posl[N], posr[N];
int a[N], L[N];
int sum[N], f[N];
int calc(int p) {
for(int i = 1; i <= n; ++i) a[i] = pos[i] = 0;
for(int i = 1; i <= m; ++i)
if(v[i] >> p & 1) ++a[l[i]], --a[r[i] + 1];
for(int i = 1; i <= n; ++i)
a[i] += a[i - 1];
int tot = 0;
for(int i = 1; i <= n; ++i) {
if(a[i] == 0) pos[i] = ++tot;
else a[i] = 1;
a[i] += a[i - 1];
}
for(int i = n; i >= 1; --i)
if(!pos[i]) posr[i] = posr[i + 1];
else posr[i] = pos[i];
for(int i = 1; i <= n; ++i)
if(!pos[i]) posl[i] = posl[i - 1];
else posl[i] = pos[i];
for(int i = 1; i <= tot; ++i) L[i] = 0;
for(int i = 1; i <= m; ++i) {
if(v[i] >> p & 1) continue;
if(a[r[i]] - a[l[i] - 1] == r[i] - l[i] + 1) return 0;
L[posl[r[i]]] = max(L[posl[r[i]]], posr[l[i]]);
}
for(int i = 1; i <= tot; ++i)
L[i] = max(L[i], L[i - 1]);
f[0] = sum[0] = 1;
for(int i = 1; i <= tot; ++i)
f[i] = (sum[i - 1] - (L[i - 1] <= 0 ? 0 : sum[L[i - 1] - 1]) + P) % P,
sum[i] = (sum[i - 1] + f[i]) % P;
int res = 0;
for(int i = L[tot]; i <= tot; ++i)
res = (res + f[i]) % P;
return res;
}
int main() {
read(n), read(k), read(m);
for(int i = 1; i <= m; ++i)
read(l[i]), read(r[i]), read(v[i]);
LL ans = 1;
for(int p = 0; p < k; ++p)
ans = ans * calc(p) % P;
printf("%lld\n",ans);
}