|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 20010;
|
|
|
|
|
|
// 线段树
|
|
|
#define mid ((l + r) >> 1)
|
|
|
#define ls (u << 1)
|
|
|
#define rs (u << 1 | 1)
|
|
|
struct Node {
|
|
|
int l, r, len;
|
|
|
int lx, rx, mx; // lx:左起最长符合条件的长度；rx:右起最长符合条件的长度；mx:整体区间内符合条件的长度
|
|
|
} tr[N << 2];
|
|
|
|
|
|
int color[N]; // 每个位置上的颜色
|
|
|
|
|
|
void pushup(int u) {
|
|
|
// 左儿子的最右端点颜色，与右儿子的最左端点颜色是否相同
|
|
|
bool flag = color[tr[ls].r] != color[tr[rs].l];
|
|
|
|
|
|
tr[u].lx = tr[ls].lx; // 左起最长，继承左儿子的左起最长
|
|
|
// 如果左儿子全部区间满足条件，并且，左儿子最右，不等于，右儿子最左，也就是继续符合条件
|
|
|
if ((tr[ls].lx == tr[ls].len) && flag) tr[u].lx = tr[ls].len + tr[rs].lx;
|
|
|
|
|
|
tr[u].rx = tr[rs].rx; // 右起最长，继承右儿子的右起最长
|
|
|
// 如果右儿子全部区间满足条件，并且，右儿子最左，不等于，左儿子最右，也就是继续符合条件
|
|
|
if ((tr[rs].rx == tr[rs].len) && flag) tr[u].rx = tr[rs].len + tr[ls].rx;
|
|
|
|
|
|
tr[u].mx = max(tr[ls].mx, tr[rs].mx);
|
|
|
if (flag) tr[u].mx = max(tr[u].mx, tr[ls].rx + tr[rs].lx); // 拼接
|
|
|
}
|
|
|
|
|
|
void build(int u, int l, int r) {
|
|
|
tr[u].l = l, tr[u].r = r, tr[u].len = r - l + 1;
|
|
|
|
|
|
if (l == r) {
|
|
|
tr[u].lx = tr[u].rx = tr[u].mx = 1; // 表演刚开始每一个鼓都是红色面朝向观众
|
|
|
return;
|
|
|
}
|
|
|
build(ls, l, mid);
|
|
|
build(rs, mid + 1, r);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
void modify(int u, int p) {
|
|
|
int l = tr[u].l, r = tr[u].r;
|
|
|
if (l == r) {
|
|
|
color[p] = !color[p]; // 红变白，白变红
|
|
|
return;
|
|
|
}
|
|
|
if (p <= mid)
|
|
|
modify(ls, p);
|
|
|
else
|
|
|
modify(rs, p);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
#ifndef ONLINE_JUDGE
|
|
|
freopen("P2253.in", "r", stdin);
|
|
|
#endif
|
|
|
int n, m;
|
|
|
cin >> n >> m;
|
|
|
|
|
|
build(1, 1, n);
|
|
|
|
|
|
while (m--) {
|
|
|
int p;
|
|
|
cin >> p;
|
|
|
modify(1, p);
|
|
|
printf("%d\n", tr[1].mx);
|
|
|
}
|
|
|
return 0;
|
|
|
} |
