题解 P9400 「DBOI」Round 1 三班不一般

Phobia · 2023-06-05 07:01:00 · 题解

显然有这样一个想法，设 f(i,j) 表示前 i 个位置，以第 i 个灯结尾的最大连续灯泡亮度大于 b 的子串长度为 j 和法的方案数。

转移方程：

直接转移显然不行，但观察到 f(i) 和 f(i-1) 之间的存在继承关系，如下图：

相当于在 f(i-1) 前面插入一个数和在后面删除一个数，然后再批量处理，故想到使用数据结构维护。

此时已经可以使用平衡树或块状链表维护，注意到至多向前插入 n 个元素，考虑开一颗线段树维护一个长度为 n+a 的数组，再用两个变量记录当前维护的左端点和右端点，初始在最右边，转移时将左、右端点往左移动一个单位。

时间复杂度 O(n\log n)，空间复杂度 O(n)。

#include <bits/stdc++.h>

using namespace std;

typedef long long i64;

const int maxn = 200005, mod = 998244353;

int n, a, b;

int tre[maxn * 8], mul[maxn * 8], m, pl, pr; // pl, pr 维护 f 数组第二维对应线段树上的编号范围

int read()
{
    int ret = 0, ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        ;
    for (; isdigit(ch); ch = getchar())
        ret = (ret << 3) + (ret << 1) + (ch & 15);
    return ret;
}

void build(int root, int l, int r)
{
    mul[root] = 1;
    if (l < r)
    {
        int mid = l + r >> 1;
        build(root << 1, l, mid);
        build(root << 1 | 1, mid + 1, r);
    }
}

void push_down(int root)
{
    if (mul[root] != 1)
    {
        tre[root << 1] = (i64)tre[root << 1] * mul[root] % mod;
        mul[root << 1] = (i64)mul[root << 1] * mul[root] % mod;
        tre[root << 1 | 1] = (i64)tre[root << 1 | 1] * mul[root] % mod;
        mul[root << 1 | 1] = (i64)mul[root << 1 | 1] * mul[root] % mod;
        mul[root] = 1;
    }
}

void modify(int root, int l, int r, int x, int v)
{
    if (l == r)
    {
        tre[root] = v;
        return;
    }
    int mid = l + r >> 1;
    push_down(root);
    if (x <= mid)
        modify(root << 1, l, mid, x, v);
    else
        modify(root << 1 | 1, mid + 1, r, x, v);
    tre[root] = (tre[root << 1] + tre[root << 1 | 1]) % mod;
}

void multiply(int root, int l, int r, int x, int y, int v)
{
    if (x <= l && r <= y)
    {
        tre[root] = (i64)tre[root] * v % mod;
        mul[root] = (i64)mul[root] * v % mod;
        return;
    }
    int mid = l + r >> 1;
    push_down(root);
    if (x <= mid)
        multiply(root << 1, l, mid, x, y, v);
    if (mid < y)
        multiply(root << 1 | 1, mid + 1, r, x, y, v);
    tre[root] = (tre[root << 1] + tre[root << 1 | 1]) % mod;
}

int sum(int root, int l, int r, int x, int y)
{
    if (l > y || r < x)
        return 0;
    if (x <= l && r <= y)
        return tre[root];
    int mid = l + r >> 1;
    push_down(root);
    return (sum(root << 1, l, mid, x, y) + sum(root << 1 | 1, mid + 1, r, x, y)) % mod;
}

int main()
{
    n = read(), a = read() - 1, b = read();
    m = n + a + 1, pr = n + a + 1, pl = n + 1;
    build(1, 1, m);
    modify(1, 1, m, pl, 1);
    for (int i = 1; i <= n; ++i)
    {
        int l = read(), r = read();
        if (l <= b)
            modify(1, 1, m, pl - 1, (i64)(min(b, r) - l + 1) * sum(1, 1, m, pl, pr) % mod);
        if (r > b)
            multiply(1, 1, m, pl, pr, r - max(b, l - 1));
        else
            multiply(1, 1, m, pl, pr, 0); // 这里等价于区间修改为 0
        --pl, --pr;
    }
    printf("%d\n", sum(1, 1, m, pl, pr));
    return 0;
}

数据结构优化 dp 实锤了。