题目描述

给定一个长度为 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;
}