JOISC2022 错误拼写 Sol

· · 题解

实在是绷不住了，做 JOISC 做到梦熊炼石原题，这下这下了。

限制 T_u\le T_v\ (u<v) 告诉你啥呢，告诉你这 [u, v] 这个区间要么全部相等，要么第一个相邻不同的位置是左边大于右边；u>v 就是反过来，要么相等要么第一个相邻不同的位置左边小于右边。

考虑 dp，f_{i,j} 表示考虑了 [i,n]，i 这个位置填的 j 这个字符。如果暴力转移就是枚举下一个不同的位置，判断合不合法并计算贡献。复杂度是 \Theta(n^2\Sigma)。

你去想判断合不合法的过程是怎么样的，就是把所有左端点 \ge i 的限制区间全扔下标上，进行一个判断。那我们发现你 i 从右边来的时候，会增加一部分区间，改变一些位置的限制条件（即转移方式）。具体地，一个位置被转移的方式有：

然后发现每个点的状态最多被改变 2 次。我们只要快速找到哪些点的覆盖状态发生了改变，用 set 维护每种状态的位置即可。复杂度 \Theta(n(\log n+\Sigma))。

signed main() {
    n = read(), m = read();
    rep(i, 1, m) {
        int x = read(), y = read(), f = 0;
        if (x == y) continue;
        if (x > y) swap(x, y), f ^= 1;
        p[x].push_back({y, f});
    }
    rep(j, 0, 25) f[n][j] = 1, ge[j] = 1;
    se.insert(n);
    per(i, n - 1, 1) {
        for (pii j : p[i]) {
            int l = i, r = j.fs, fl = j.sc;
            if (fl) {
                auto it = se.lower_bound(l + 1);
                while (it != se.end() && *it <= r) {
                    s1.insert(*it);
                    rep(k, 0, 25) g1[k] += f[*it][k], ge[k] -= f[*it][k];
                    se.erase(it++);
                }
                it = s0.lower_bound(l + 1);
                while (it != s0.end() && *it <= r) {
                    s2.insert(*it);
                    rep(k, 0, 25) g0[k] -= f[*it][k];
                    s0.erase(it++);
                }
            } else {
                auto it = se.lower_bound(l + 1);
                while (it != se.end() && *it <= r) {
                    s0.insert(*it);
                    rep(k, 0, 25) g0[k] += f[*it][k], ge[k] -= f[*it][k];
                    se.erase(it++);
                }
                it = s1.lower_bound(l + 1);
                while (it != s1.end() && *it <= r) {
                    s2.insert(*it);
                    rep(k, 0, 25) g1[k] -= f[*it][k];
                    s1.erase(it++);
                }
            }
        }
        int s = 0;
        rep(j, 0, 25) (s += ge[j]) %= mod;
        rep(j, 0, 25) f[i][j] += (s - ge[j] % mod + mod) % mod;
        s = 0;
        per(j, 25, 0) {
            (f[i][j] += s) %= mod;
            (s += g0[j] % mod) %= mod;
        }
        s = 0;
        rep(j, 0, 25) {
            (f[i][j] += s) %= mod;
            (s += g1[j]) %= mod;
        }
        rep(j, 0, 25) f[i][j]++, f[i][j] %= mod;
        se.insert(i);
        rep(j, 0, 25) ge[j] += f[i][j];
    }
    int ans = 0;
    rep(j, 0, 25) (ans += f[1][j]) %= mod;
    write(ans);
    return 0;
}