題目描述

給定一個長度為?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;
}