维护二进制字符序列的最长交替连续子串，支持单点翻转。
OJ: luogu
题目 ID: P6492
难度:普及+/提高
标签:线段树字符串交替序列python
日期: 2026-07-16 23:59
题意
初始全为 L，每次翻转一个位置的 L/R，输出最长相邻字符交替的连续子串长度。
思路
节点保存首字符、尾字符、交替前缀、交替后缀和最大交替段。合并时只有左尾和右首不同，跨越中点的后缀与前缀才能拼接；若整个左（右）段都是交替段，前（后）缀也可以延长。
Python 知识
^= 1是布尔状态翻转的简洁写法。- 初始化全相同序列时不必逐叶建值，只需把每个节点的长度作为交替前后缀。
- 首尾状态用
bytearray，长度统计用array("i")，大规模节点也能保持紧凑。
代码
python
import sys
from array import array
sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
n, operations = map(int, input().split())
first = bytearray(4 * n)
last = bytearray(4 * n)
prefix = array("i", [0]) * (4 * n)
suffix = array("i", [0]) * (4 * n)
best = array("i", [0]) * (4 * n)
def pull(node, left_length, right_length):
left, right = node * 2, node * 2 + 1
different = last[left] != first[right]
first[node] = first[left]
last[node] = last[right]
prefix[node] = prefix[left] + prefix[right] if different and prefix[left] == left_length else prefix[left]
suffix[node] = suffix[right] + suffix[left] if different and suffix[right] == right_length else suffix[right]
best[node] = max(best[left], best[right], suffix[left] + prefix[right] if different else 0)
def build(node, left, right):
prefix[node] = suffix[node] = best[node] = right - left + 1
if left == right:
return
middle = (left + right) // 2
build(node * 2, left, middle)
build(node * 2 + 1, middle + 1, right)
pull(node, middle - left + 1, right - middle)
def update(node, left, right, position):
if left == right:
first[node] ^= 1
last[node] = first[node]
return
middle = (left + right) // 2
if position <= middle:
update(node * 2, left, middle, position)
else:
update(node * 2 + 1, middle + 1, right, position)
pull(node, middle - left + 1, right - middle)
build(1, 1, n)
answers = []
for _ in range(operations):
position = int(input())
update(1, 1, n, position)
answers.append(str(best[1]))
print("\n".join(answers))原有 C++ 版本仍保留：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-16 23:46
* update_at: 2026-07-16 23:46
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}复杂度
每次单点翻转 O(log n)，空间 O(n)。
总结
“交替”只依赖相邻边界是否不同，因此首尾字符加四个长度统计量就足够合并。