线段树优化dp

飞马祝福语

这是一个区间计数问题，可以考虑用线段树优化 dp
不妨设模版串为 P\bold{P}，文本串为 str\bold{str}

  • 根据 str\bold{str} 建立线段树，f(p,l,r)f(p, l, r) 表示线段树 pp 这个节点对应的 str\bold{str} 区间中，
    包含子串 P[l⋯r]\bold{P}[l \cdots r] 的个数，由此可以写出状态转移方程

    f(p,l,r)=f(p≪1,l,r)+f(p≪1∣1,l,r)+∑k=lr−1(f(p≪1,l,k)⋅f(p≪1∣1,k+1,r))f(p, l, r) = f(p \ll 1, l, r) + f(p \ll 1 \mid 1, l, r) + \sum_{k = l}^{r-1} \left( f(p \ll 1, l, k) \cdot f(p \ll 1 \mid 1, k+1, r) \right)

  • 对于区间修改，[li,ri]→ch[l_i, r_i] \to ch，可以使用延迟标记，执行 change(1,li,ri,ch)\bold{change}(1, l_i, r_i, ch)
    pull\bold{pull} 函数即执行 dp 方程
    push(p)\bold{push}(p) 函数，以 lson(p)\bold{lson}(p) 为例子，len←(lson(p).r−lson(p).l+1)len \leftarrow (\bold{lson}(p).r - \bold{lson}(p).l + 1)
    ch←tag(p)ch \leftarrow \bold{tag}(p)，此时令 f(lson(p),i,i)=1⋅len,其中 P(i)=chf(\bold{lson}(p), i, i) = 1 \cdot len, \quad \text{其中 } \bold{P}(i) = ch
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
const int maxn = 1e5 + 10, mod = 998244353;
char str[maxn];
const string P = "FeiMa";

ll f[maxn<<2][5][5];

class segTree {
public:
    struct node {
        int l, r;
        char tag;
    };
    vector<node> t;

    int n;
    segTree() = default;
    segTree(int _n) : n(_n) {
        t.resize(n<<2);
    }
    void clear() {
        t = vector<node> (n<<2, node());
    }

    inline void clear(int p) {
        for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) {
            f[p][i][j] = 0;
        }
    }
    inline void pull(int p) {
        for (int l = 0; l < 5; l++) for (int r = l; r < 5; r++) {
            f[p][l][r] = (f[p<<1][l][r] + f[p<<1|1][l][r]) % mod;
            for (int k = l; k < r; k++) 
                f[p][l][r] = (f[p][l][r] + f[p<<1][l][k] * f[p<<1|1][k+1][r] % mod) % mod;
        }
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r; t[p].tag = 0;
        clear(p);
        if (l == r) {
            char ch = str[l];
            for (int i = 0; i < 5; i++) if (P[i] == ch) f[p][i][i] = 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(p<<1, l, mid);
        build(p<<1|1, mid+1, r);

        pull(p);
    }

    void push(int p) {
        // use only if tag[p] != 0
        if (!t[p].tag) return;
        char ch = t[p].tag;
        t[p<<1].tag = t[p<<1|1].tag = ch, t[p].tag = 0;

        clear(p<<1);
        int len = t[p<<1].r - t[p<<1].l + 1;
        for (int i = 0; i < 5; i++) if (P[i] == ch) f[p<<1][i][i] = len;

        clear(p<<1|1);
        len = t[p<<1|1].r - t[p<<1|1].l + 1;
        for (int i = 0; i < 5; i++) if (P[i] == ch) f[p<<1|1][i][i] = len;
    }

    void change(int p, const int l, const int r, char ch) {
        if (l <= t[p].l && t[p].r <= r) {
            t[p].tag = ch;
            
            clear(p);
            for (int i = 0; i < 5; i++) if (P[i] == ch) f[p][i][i] = t[p].r - t[p].l + 1;
            return;
        }
        
        push(p);

        int mid = (t[p].l + t[p].r) >> 1;
        if (l <= mid) change(p<<1, l, r, ch);
        if (r > mid) change(p<<1|1, l, r, ch);

        pull(p);
    }

} seg(maxn);
int n, q;

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    int cas;
    cin >> cas;

    while (cas--) {
        // init
        init();
        scanf("%d%d", &n, &q);
        scanf("%s", str+1);
        assert(strlen(str+1) == n);

        // build
        seg.build(1, 1, n);

        while (q--) {
            int li, ri;
            char x[2];
            scanf("%d%d%s", &li, &ri, x);

            seg.change(1, li, ri, x[0]);
            ll res = f[1][0][4];
            printf("%lld\n", res);
        }
    }
}

小米邀请赛：线段树优化dp

Phone Network

题意，有一个长度为 nn 的序列，每个点权值为在范围 [1,m][1, m] 内，并且保证每个值都出现过
对每个 i(1⩽i⩽m)i(1 \leqslant i \leqslant m) 询问包含权值 [1,i][1, i] 的最小区间长度

具体来说，f(i,x)f(i, x) 表示以 [i⋯ )[i \cdots) 作为左端点，并且包含 [1⋯x][1\cdots x] 所有值（即编号为 [1⋯x][1\cdots x] 的网络）
此时最近的右端点，记为 f(i,x)f(i, x)
另外用 Ax[⋯ ]\bm{A}_x[\cdots] 表示 xx 网络出现的位置

  • 很容易想到一种 O(n2)O(n^2) 的算法，状态转移方程是 f(i,x)=max⁡(f(i,x−1),min⁡(Ax[⋯ ]))f(i, x) = \max (f(i, x-1), \min (\bm{A}_x[\cdots]))
    用 last\text{last} 记录 Ax[⋯ ]\bm{A}_x[\cdots] 中离 ii 最近的位置
    那么 f(i,x)=max⁡(f(i,x−1),last)f(i, x) = \max (f(i, x-1), \text{last})
  • 考虑优化，对于 for ∀x∈[1⋯m]\textbf{for} \ \forall x \in [1\cdots m]
    尝试维护 ∀i∈[1⋯n]\forall i \in [1\cdots n] 中的 fx(i)f_x(i)，其中保证 [i⋯fx(i)][i\cdots f_x(i)] 中 [1⋯x][1\cdots x] 的每个数都出现
    这样可以用 min⁡(fx(i)−i+1)\min (f_x(i) - i + 1) 来更新全局的 resres
  • Ax={p1,⋯pj−1,pj⋯pk}\bm{A}_x = \{p_1, \cdots p_{j-1}, p_j \cdots p_k\}，当 pj−1→pjp_{j-1} \to p_j 转移的时候，考虑区间 [pj−1+1⋯pj][p_{j-1}+1\cdots p_j]
    对于 ∀ i⩽pj−1\forall \ i \leqslant p_{j-1}，pjp_j 处出现的 xx 不影响 fx(i)f_x(i) 的值
    而 ∀ i∈[pj−1+1⋯pj]\forall \ i \in [p_{j-1} + 1 \cdots p_j]，要更新所有的 fx(i)←max⁡(fx(i),pj)f_x(i) \leftarrow \max (f_x(i), p_j)
    但注意到对于 ∀i∈[pj−1+1⋯pj]\forall i \in [p_{j-1}+1 \cdots p_j]，pjp_j 只会影响到 fx(i)<pjf_x(i) < p_j 的 ii
    也就是说，我们只需要更新 [pj−1+1,pj][p_{j-1}+1, p_j] 的某一段子区间即可，不妨设为 [pj−1+1,pos][p_{j-1}+1, pos]
    注意单调性，对于 i1<i2i_1 < i_2，有 fx(i1)⩽fx(i2)f_x(i_1) \leqslant f_x(i_2)
    i⩽posi \leqslant pos, fx(i)⩽fx(pos)f_x(i) \leqslant f_x(pos)，只需要修改 [pj−1+1,pos][p_{j-1}+1, pos] 即可
  • 要求出 pospos，可以考虑在区间 i∈[1⋯n]i \in [1\cdots n] 上建线段树，节点 uu 表示区间 [tu.l,tu.r][t_u.l, t_u.r]
    tu.ft_u.f 维护 ∀i∈[tu.l,tu.r]\forall i \in [t_u.l, t_u.r] 的 fx(i)f_x(i) 信息
    在线段树上二分查找，找到满足 tu.f<pjt_u.f < p_j 的最大叶节点，pos←tu.lpos \leftarrow t_u.l
  • 接下来在线段树找到区间 u=[pj−1+1,pos]u = [p_{j-1}+1, pos]，并且执行区间赋值 tu.f←pjt_u.f \leftarrow p_j
    此时 i∈[tu.l,tu.r]=[pj−1+1,pos]i \in [t_u.l, t_u.r] = [p_{j-1}+1, pos] 所有的 fx(i)f_x(i) 都相等
    最短的包含 [1⋯x][1\cdots x] 所有数的区间的长度 len(x)=tu.f−tu.r+1\textbf{len}(x) = t_u.f - t_u.r + 1
    自底向上 pull\textbf{pull} 取 min⁡\min，最后 t1.lent_1.len 就是 len(x)\textbf{len}(x) 对应的答案
    特别地，Ax={p1,⋯ ,pk}\bm{A}_x = \{p_1, \cdots, p_k\}，对于 i∈[pk+1,⋯n]i \in [p_{k}+1, \cdots n] 这一段，
    不存在满足 [1⋯x][1\cdots x] 所有数都出现的区间段，这里只要将这个区间段的 tu.f←+∞t_u.f \leftarrow +\infty
    这样更新 min⁡\min 的时候就用不到这一段了
  • 综上所述，线段树维护 ff，表示 fx(i)f_x(i)，另外需维护 min⁡\min，表示 [tu.l,tu.r][t_u.l, t_u.r] 对应的最小 len(x)\text{len}(x)
    初始化 min⁡\min 为 +∞+\infty，ff 为 00，每次处理完 A=p1⋯pk\bm{A}={p_1\cdots p_k} 时
    将 [pk+1,n][p_k+1, n] 的 ff 置为 +∞+\infty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
const int maxn = 2e5 + 10, inf = 0x3f3f3f3f;
int n, m;
vector<int> G[maxn];

class SegTree {
public:
    struct node {
        int l, r;
        int tag, len, f;
    };

    int tot = 0;
    vector<node> t;
    SegTree() = default;
    SegTree(int _tot) : tot(_tot) {
        assert(_tot > 0);
        t.resize(tot << 2);
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l >= r) {
            t[p].f = 0, t[p].len = inf;
            return;
        }
        int mid = (l+r) >> 1;
        build(p<<1, l, mid);
        build(p<<1|1, mid+1, r);
    }

    void push(int p) {
        if (!t[p].tag) return;
        int fv = t[p].tag; t[p].tag = 0;

        t[p<<1].tag = fv;
        t[p<<1].f = fv;
        t[p<<1].len = fv - t[p<<1].r + 1;

        t[p<<1|1].tag = fv;
        t[p<<1|1].f = fv;
        t[p<<1|1].len = fv - t[p<<1|1].r + 1;
    }

    void pull(int p) {
        t[p].len = min(t[p<<1].len, t[p<<1|1].len);
        t[p].f = min(t[p<<1].f, t[p<<1|1].f);
    }

    void change(int p, const int l, const int r, int fv) {
        if (l <= t[p].l && t[p].r <= r) {
            t[p].tag = fv;
            t[p].f = fv;
            t[p].len = fv - t[p].r + 1;
            return;
        }
        push(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (l <= mid) change(p<<1, l, r, fv);
        if (r > mid) change(p<<1|1, l, r, fv);
        pull(p);
        return;
    }

    int find(int p, const int l, const int r, int fv) {
        if (t[p].l == t[p].r) return t[p].l;
        push(p);

        int mid = (t[p].l + t[p].r) >> 1;
        int res = -1;
        if (r > mid && t[p<<1|1].f < fv) res = find(p<<1|1, l, r, fv);
        if (res != -1) return res;
        if (l <= mid && t[p<<1].f < fv) res = find(p<<1, l, r, fv);
        return res;
    }
} seg(maxn);

void solve() {
    for (int x = 1; x <= m; x++) {
        for (int j = 1; j < G[x].size(); j++) {
            int l = G[x][j-1] + 1, r = G[x][j];
            // [l, pos] to be changed
            int pos = seg.find(1, l, r, r);
            if (pos == -1) continue;
            seg.change(1, l, pos, r);
        }
        seg.change(1, G[x].back()+1, n, inf);
        int res = seg.t[1].len;
        printf("%d ", res);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) G[i].push_back(0);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        G[x].push_back(i);
    }

    // init seg tree
    seg.build(1, 1, n);

    solve();
}