题意
给一个只由小写字母构成的长度为n的字符串$s[1:n]$,做q次操作,每次修改其中 $s[a_i]$ 为 $c_i$,每次询问完整的区间上由某一个字符构成的最长连续子串的长度是多少?
数据范围
$n\le{}1e5, q\le{1e5}$
题解
看评论区说,这是一个线段树的板子题。
更一般的情况是,给一个区间,做q次询问,询问可以做任意区间的区间染色,也可以询问某个任意区间的最长连续同色区间的长度。我比较喜欢考虑一般化的问题,如果一般化的问题能和特殊化的问题在同样复杂度的时间内解决,我更希望解决一般化的问题,所以下面我们来考察这个问题。
比赛时候,我的首先想法是维护26个线段树,每个线段树只维护其中一个字母的状态,比如a树,为a的地方就是1,不是的就是0,我们只需要维护26个线段树的状态然后做最大子段和就行了。如果字符集的大小为V,时间复杂度为$O(V(n+q)logn)$,空间复杂度$O(Vn)$,时间复杂度和空间复杂度双双爆炸(他奶奶滴)。主要是比赛的时候想到了最大子段和的模板题,就一直在想怎么往最大子段和里套,没想着自己重新写pushup函数。
接下来我们来考虑正确的做法,这个做法是不依赖于字符集的规模的,只需要维护一棵线段树,时间复杂度$O((n+q)logn)$。但是也用到了最大子段和的想法,如果不会最大子段和的求法,可能应该先看一下AcWing 245. 你能回答这些问题吗会更好理解。
我们全局维护s数组就可以了,用s数组来指导lsum,rsum和totsum怎么合并。因为只有单点修改,我们只写pushup函数就可以了。状态表示和最大子段和是完全相同的。
lsum表示包括s[tree[now].left]这个字符的最大连续长度
rsum表示包括s[tree[now].right]这个字符的最大连续长度
totsum表示包括s[tree[now].left : tree[now].right]这个区间上的最大连续长度
如果已经理解了最大子段和,我们应该不难理解这三个状态的状态转移。
以lsum为例,当前的lsum在一般情况下就等于它左孩子的lsum,而如果左孩子的lsum等于左孩子能表示的区间长度,而且左孩子的字符和右孩子左边界的字符是相同的,那左孩子和右孩子就可以贯通;rsum同理。
totsum在一般情况下就是左孩子totsum和右孩子totsum的最大值,但是需要考虑合并的时候,如果左孩子的右边界和右孩子的左边界相同,那么左孩子的rsum和右孩子的lsum就可以贯通,我们就可以对应写出pushup函数了。
当然可能有人要问,你是怎么想到要表示lsum和rsum的?回答是,你要看想表示totsum需要哪些信息才能维护,这有点像分治的想法,分治的过程交给孩子完成,合并的过程就是额外情况,就像这个题是需要知道左孩子和右孩子就能知道合并的情况。所以这才是思考问题的过程,而不是看着答案推。
pushup函数如下:
void Pushup(int k){
tree[k].sum = max(tree[lson(k)].sum, tree[rson(k)].sum);
if(s[tree[lson(k)].right] == s[tree[rson(k)].left])
tree[k].sum = max(tree[k].sum, tree[lson(k)].rsum + tree[rson(k)].lsum);
tree[k].lsum = tree[lson(k)].lsum;
if(tree[lson(k)].lsum == tree[lson(k)].right - tree[lson(k)].left + 1 && s[tree[lson(k)].right] == s[tree[rson(k)].left])
tree[k].lsum += tree[rson(k)].lsum;
tree[k].rsum = tree[rson(k)].rsum;
if(tree[rson(k)].rsum == tree[rson(k)].right - tree[rson(k)].left + 1 && s[tree[lson(k)].right] == s[tree[rson(k)].left])
tree[k].rsum += tree[lson(k)].rsum;
}
完整代码如下:
/**
* @file template.cpp
* @author Emanual20(Emanual20@foxmail.com)
* @brief For Codeforces, Atcoder or some other OJs else
* @version 0.1
* @date 2022-03-20
*
* @copyright Copyright (c) 2022
*
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define father(x) ((x) >> 1)
const int maxn = 2e5 + 10;
struct seg_node{
int left, right;
int sum, lsum, rsum;
};
struct seg_tree{
public:
seg_node tree[4 * maxn];
char s[maxn];
void initarrays(string str){
int lens = str.length();
for(int i = 0; i < lens; i++){
s[i + 1] = str[i];
}
}
void Pushup(int k){
tree[k].sum = max(tree[lson(k)].sum, tree[rson(k)].sum);
if(s[tree[lson(k)].right] == s[tree[rson(k)].left])
tree[k].sum = max(tree[k].sum, tree[lson(k)].rsum + tree[rson(k)].lsum);
tree[k].lsum = tree[lson(k)].lsum;
if(tree[lson(k)].lsum == tree[lson(k)].right - tree[lson(k)].left + 1 && s[tree[lson(k)].right] == s[tree[rson(k)].left])
tree[k].lsum += tree[rson(k)].lsum;
tree[k].rsum = tree[rson(k)].rsum;
if(tree[rson(k)].rsum == tree[rson(k)].right - tree[rson(k)].left + 1 && s[tree[lson(k)].right] == s[tree[rson(k)].left])
tree[k].rsum += tree[lson(k)].rsum;
}
void build(int left, int right, int k = 1){
tree[k].left = left, tree[k].right = right;
if (left == right){
tree[k].sum = tree[k].lsum = tree[k].rsum = 1;
return;
}
int mid = (left + right) >> 1;
build(left, mid, lson(k));
build(mid + 1, right, rson(k));
Pushup(k);
}
void Update_seg(int l, int r, int x, int y, char C, int k = 1){
if (x <= l && r <= y){
s[x] = C;
return;
}
int mid = (l + r) >> 1;
if(x <= mid) Update_seg(l, mid, x, y, C, lson(k));
if(y > mid) Update_seg(mid + 1, r, x, y, C, rson(k));
Pushup(k);
}
int Query_seg(int l, int r, int x, int y, int k = 1){
int ret = 0;
if (x <= l && r <= y){
ret = tree[k].sum;
return ret;
}
int mid = (l + r) >> 1;
if (mid >= x) ret += Query_seg(l, mid, x, y, lson(k));
if (mid < y) ret += Query_seg(mid + 1, r, x, y, rson(k));
return ret;
}
};
class Solution {
public:
const int maxn = 2e5 + 10;
vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
int lens = s.length();
vector<int> ret(queryCharacters.size());
seg_tree st;
st.initarrays(s);
st.build(1, lens);
for (int i = 0; i < queryCharacters.size(); i++){
int nq_pos = queryIndices[i] + 1;
char nq_ch = queryCharacters[i];
st.Update_seg(1, lens, nq_pos, nq_pos, nq_ch);
auto nq_ans = st.Query_seg(1, lens, 1, lens);
ret[i] = nq_ans;
}
return ret;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}