python/TangDou/AcWing/SegmentTree/P2253.cpp

#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;
}