题目描述
难度分:2400
输入n(1≤n≤105),q(1≤q≤105)和长为n的字符串s,只包含a
,b
,c
。
然后输入q个操作,每个操作输入i(1≤i≤n)和c(c是a
或者b
或者c
)。
每个操作会把s[i]改成c。每次操作后,要使s不包含子序列abc
,至少要删除多少个字母?
注:子序列不一定连续。
输入样例
9 12
aaabccccc
4 a
4 b
2 b
5 a
1 b
6 b
5 c
2 a
1 a
5 a
6 b
7 b
输出样例
0
1
2
2
1
2
1
2
2
2
2
2
算法
线段树优化DP
如果是个静态的字符串,这个题的DP
思路是比较好想的,但这个字符串可以动态改变所以需要数据结构加以优化。
状态定义
线段树每个节点所管辖的区间范围内,维护以下6个信息:
- 消除所有
a
需要操作的最少次数a。 - 消除所有
b
需要操作的最少次数b。 - 消除所有
c
需要操作的最少次数c。 - 消除所有
ab
需要操作的最少次数ab。 - 消除所有
bc
需要操作的最少次数bc。 - 消除所有
abc
需要操作的最少次数abc。
状态转移
每当修改字符串的一个字符s[i]=c,就更新线段树根所有节点的6个信息,最终答案就是根节点的abc值。
对于某个节点(假设这个节点管辖区间为[l,r])的左右两个子节点lchild、rchild,如果两个区间的信息要合并,状态转移如下:
- 要消除[l,r]内部的所有
a
,就把左右两个子区间的a
都消除,状态转移方程为lchild.a+rchild.a。 - 要消除[l,r]内部的所有
b
,就把左右两个子区间的b
都消除,状态转移方程为lchild.b+rchild.b。 - 要消除[l,r]内部的所有
c
,就把左右两个子区间的c
都消除,状态转移方程为lchild.c+rchild.c。 - 要消除[l,r]内部的所有
ab
,有两种方式:把左区间的a
消除+把右区间的ab
消除;把左区间的ab
消除+把右区间的b
消除。两种策略选较小值转移,状态转移方程为min(lchild.a+rchild.ab,lchild.ab+rchild.b)。 - 要消除[l,r]内部的所有
bc
,有两种方式:把左区间的b
消除+把右区间的bc
消除;把左区间的bc
消除+把右区间的c
消除。两种策略选较小值转移,状态转移方程为min(lchild.b+rchild.bc,lchild.bc+rchild.c)。 - 要消除[l,r]内部的所有
abc
,有三种方式:把左区间的a
消除+把右区间的abc
消除;把左区间的abc
消除+把右区间的c
消除;把左区间的ab
消除+把右区间的bc
消除。三种策略选较小值转移,状态转移方程为min(lchild.a+rchild.abc,lchild.abc+rchild.c,lchild.ab+rchild.bc)。
复杂度分析
时间复杂度
线段树初始化的时间复杂度为O(nlog2n)。q次询问,每次状态转移就是线段树进行单点修改的时间复杂度,q条询问的总时间复杂度为O(qlog2n)。因此,整个算法的时间复杂度为O((n+q)log2n)。
空间复杂度
线段树的空间复杂度为O(n),每次状态转移需要递归,递归深度是O(log2n),为状态转移时的空间复杂度。所以空间瓶颈就是线段树的空间消耗,整个算法的额外空间复杂度为O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, q;
char s[N];
class SegmentTree {
public:
struct Info {
int l, r;
LL a, b, c, ab, bc, abc;
Info() {}
Info(int left, int right, LL val) {
l = left;
r = right;
a = b = c = ab = bc = abc = 0;
if(val == 0) a = 1;
if(val == 1) b = 1;
if(val == 2) c = 1;
}
} seg[N<<2];
explicit SegmentTree() {}
void build(int u, int l, int r) {
if(l == r) {
seg[u] = Info(l, r, s[r] - 'a');
}else {
int mid = l + r >> 1;
build(u<<1, l, mid);
build(u<<1|1, mid + 1, r);
pushup(u);
}
}
void modify(int pos, LL val) {
modify(1, pos, val);
}
Info query(int l, int r) {
return query(1, l, r);
}
private:
void modify(int u, int pos, LL val) {
if(seg[u].l == pos && seg[u].r == pos) {
seg[u] = Info(pos, pos, val);
}else {
int mid = seg[u].l + seg[u].r >> 1;
if(pos <= mid) {
modify(u<<1, pos, val);
}else {
modify(u<<1|1, pos, val);
}
pushup(u);
}
}
Info query(int u, int l, int r) {
if(l <= seg[u].l && seg[u].r <= r) {
return seg[u];
}
int mid = seg[u].l + seg[u].r >> 1;
if(r <= mid) {
return query(u<<1, l, r);
}else if(mid < l) {
return query(u<<1|1, l, r);
}else {
return merge(query(u<<1, l, r), query(u<<1|1, l, r));
}
}
void pushup(int u) {
seg[u] = merge(seg[u<<1], seg[u<<1|1]);
}
Info merge(const Info& lchild, const Info& rchild) {
Info info;
info.l = lchild.l;
info.r = rchild.r;
info.a = lchild.a + rchild.a;
info.b = lchild.b + rchild.b;
info.c = lchild.c + rchild.c;
info.ab = min(lchild.a + rchild.ab, lchild.ab + rchild.b);
info.bc = min(lchild.b + rchild.bc, lchild.bc + rchild.c);
info.abc = min({lchild.a + rchild.abc, lchild.ab + rchild.bc, lchild.abc + rchild.c});
return info;
}
};
int main() {
scanf("%d%d", &n, &q);
scanf("%s", s + 1);
SegmentTree seg;
seg.build(1, 1, n);
int pos;
char c;
for(int i = 1; i <= q; i++) {
cin >> pos >> c;
seg.modify(pos, c - 'a');
printf("%lld\n", seg.query(1, n).abc);
}
return 0;
}