线段树优化dp

飞马祝福语

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

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

    f(p,l,r)=f(p1,l,r)+f(p11,l,r)+k=lr1(f(p1,l,k)f(p11,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).rlson(p).l+1)len \leftarrow (\bold{lson}(p).r - \bold{lson}(p).l + 1)
    chtag(p)ch \leftarrow \bold{tag}(p),此时令f(lson(p),i,i)=1len,其中 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(1im)i(1 \leqslant i \leqslant m) 询问包含权值[1,i][1, i] 的最小区间长度

具体来说,f(i,x)f(i, x) 表示以[i)[i \cdots) 作为左端点,并且包含[1x][1\cdots x] 所有值(即编号为[1x][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,x1),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,x1),last)f(i, x) = \max (f(i, x-1), \text{last})
  • 考虑优化,对于for x[1m]\textbf{for} \ \forall x \in [1\cdots m]
    尝试维护i[1n]\forall i \in [1\cdots n] 中的fx(i)f_x(i),其中保证[ifx(i)][i\cdots f_x(i)][1x][1\cdots x] 的每个数都出现
    这样可以用min(fx(i)i+1)\min (f_x(i) - i + 1) 来更新全局的resres
  • Ax={p1,pj1,pjpk}\bm{A}_x = \{p_1, \cdots p_{j-1}, p_j \cdots p_k\},当pj1pjp_{j-1} \to p_j 转移的时候,考虑区间[pj1+1pj][p_{j-1}+1\cdots p_j]
    对于 ipj1\forall \ i \leqslant p_{j-1}pjp_j 处出现的xx 不影响fx(i)f_x(i) 的值
     i[pj1+1pj]\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[pj1+1pj]\forall i \in [p_{j-1}+1 \cdots p_j]pjp_j 只会影响到fx(i)<pjf_x(i) < p_jii
    也就是说,我们只需要更新[pj1+1,pj][p_{j-1}+1, p_j] 的某一段子区间即可,不妨设为[pj1+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)
    iposi \leqslant pos,fx(i)fx(pos)f_x(i) \leqslant f_x(pos),只需要修改[pj1+1,pos][p_{j-1}+1, pos] 即可
  • 要求出pospos,可以考虑在区间i[1n]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最大叶节点postu.lpos \leftarrow t_u.l
  • 接下来在线段树找到区间u=[pj1+1,pos]u = [p_{j-1}+1, pos],并且执行区间赋值tu.fpjt_u.f \leftarrow p_j
    此时i[tu.l,tu.r]=[pj1+1,pos]i \in [t_u.l, t_u.r] = [p_{j-1}+1, pos] 所有的fx(i)f_x(i) 都相等
    最短的包含[1x][1\cdots x] 所有数的区间的长度len(x)=tu.ftu.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] 这一段,
    不存在满足[1x][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++\inftyff00,每次处理完A=p1pk\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();
}