题目描述
给定一个长度为 n 的字符序列 a，初始时序列中全部都是字符 L。
有 q 次修改，每次给定一个 x，若 ax 为 L，则将 ax 修改成 R，否则将 ax 修改成 L。
对于一个只含字符 L，R 的字符串 s，若其中不存在连续的 L 和 R，则称 s 满足要求。
每次修改后，请输出当前序列 a 中最长的满足要求的连续子串的长度。
输入格式
第一行有两个整数，分别表示序列的长度 n 和修改操作的次数 q。
接下来 q 行，每行一个整数，表示本次修改的位置 x。
输出格式
对于每次修改操作，输出一行一个整数表示修改 a 中最长的满足要求的子串的长度。
输入输出样例
输入 #1复制
6 2 2 4
输出 #1复制
3 5
输入 #2复制
6 5 4 1 1 2 6
输出 #2复制
3 3 3 5 6
说明/提示
数据规模与约定
对于全部的测试点，保证 1≤n,q≤2×105，1≤x≤n。
说明
题目译自 COCI2010-2011 CONTEST #6 T5 STEP，翻译来自 @一扶苏一。
代码实现：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
struct SegmentNode {
int left_val; // 左端点的值
int right_val; // 右端点的值
int left_max_len; // 左端连续相同值的最大长度
int right_max_len; // 右端连续相同值的最大长度
int max_len; // 区间内连续相同值的最大长度
int interval_len; // 区间长度
};
SegmentNode tree[MAXN << 2];
int n, q; // q代替m表示查询次数
// 合并子节点信息到父节点
void merge(int node) {
int left_child = node << 1;
int right_child = node << 1 | 1;
tree[node].left_val = tree[left_child].left_val;
tree[node].right_val = tree[right_child].right_val;
tree[node].left_max_len = tree[left_child].left_max_len;
tree[node].right_max_len = tree[right_child].right_max_len;
tree[node].max_len = max(tree[left_child].max_len, tree[right_child].max_len);
if (tree[left_child].right_val != tree[right_child].left_val) {
tree[node].max_len = max(tree[node].max_len, tree[left_child].right_max_len + tree[right_child].left_max_len);
if (tree[left_child].max_len == tree[left_child].interval_len) {
tree[node].left_max_len += tree[right_child].left_max_len;
}
if (tree[right_child].max_len == tree[right_child].interval_len) {
tree[node].right_max_len += tree[left_child].right_max_len;
}
}
}
// 构建线段树
void build(int left, int right, int node) {
tree[node].interval_len = right - left + 1;
if (left == right) {
tree[node].left_val = 1;
tree[node].right_val = 1;
tree[node].left_max_len = 1;
tree[node].right_max_len = 1;
tree[node].max_len = 1;
return;
}
int mid = (left + right) / 2;
build(left, mid, left_child);
build(mid + 1, right, right_child);
merge(node);
}
// 单点更新
void update(int pos, int left, int right, int node) {
if (left == right) {
tree[node].left_val ^= 1;
tree[node].right_val = tree[node].left_val;
return;
}
int mid = (left + right) / 2;
if (pos <= mid) update(pos, left, mid, left_child);
else update(pos, mid + 1, right, right_child);
merge(node);
}
int main() {
scanf("%d %d", &n, &q);
build(1, n, 1);
int x;
while (q--) {
scanf("%d", &x);
update(x, 1, n, 1);
printf("%d\n", max(tree[1].max_len, max(tree[1].left_max_len, tree[1].right_max_len)));
}
return 0;
}