#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

namespace dts
{
    struct st_node
    {
        int l,r,mid,lans,rans,ans;
        
        int len()
        {
            return r-l+1;
        }
    };
    
    int n,q,a[(1<<19)+1];
    st_node st[(1<<20)+2];
    #define lc(now) ((now)<<1)
    #define rc(now) ((now)<<1|1)
    
    void process(int now)
    {
        st[now].lans=st[lc(now)].lans;
        st[now].rans=st[rc(now)].rans;
        if (a[st[lc(now)].r]!=a[st[rc(now)].l])
        {
            if (st[lc(now)].lans==st[lc(now)].len())
                st[now].lans=st[lc(now)].len()+st[rc(now)].lans;
            if (st[rc(now)].rans==st[rc(now)].len())
                st[now].rans=st[rc(now)].len()+st[lc(now)].rans;
        }
        st[now].ans=max(st[lc(now)].ans,st[rc(now)].ans);
        if (a[st[lc(now)].r]!=a[st[rc(now)].l])
            st[now].ans=max(st[now].ans,st[lc(now)].rans+st[rc(now)].lans);
    }
    
    void st_build(int now,int l,int r)
    {
        st[now].l=l,st[now].r=r;
        if (l<r)
        {
            st[now].mid=(l+r)>>1;
            st_build(lc(now),l,st[now].mid);
            st_build(rc(now),st[now].mid+1,r);
            process(now);
        }
        else
            st[now].ans=st[now].lans=st[now].rans=1;
    }
    
    void st_update(int now,int pos)
    {
        if (st[now].l==pos&&pos==st[now].r)
        {
            a[st[now].l]^=1;
        }
        else
        {
            if (pos<=st[now].mid)
                st_update(lc(now),pos);
            else if (st[now].mid+1<=pos)
                st_update(rc(now),pos);
            process(now);
        }
    }
    
    void st_ask(int now,int l,int r,int &lans,int &rans,int &ans)
    {
        if (st[now].l==l&&r==st[now].r)
            lans=st[now].lans,rans=st[now].rans,ans=st[now].ans;
        else if (r<=st[now].mid)
            st_ask(lc(now),l,r,lans,rans,ans);
        else if (st[now].mid+1<=l)
            st_ask(rc(now),l,r,lans,rans,ans);
        else
        {
            int l_lans,l_rans,l_ans,r_lans,r_rans,r_ans;
            st_ask(lc(now),l,st[now].mid,l_lans,l_rans,l_ans);
            st_ask(rc(now),st[now].mid+1,r,r_lans,r_rans,r_ans);
            lans=l_lans,rans=r_rans;
            if (a[st[now].mid]!=a[st[now].mid+1])
            {
                if (l_lans==st[now].mid-l+1)
                    lans=(st[now].mid-l+1)+r_lans;
                if (r_rans==r-(st[now].mid+1)+1)
                    rans=(r-(st[now].mid+1)+1)+l_rans;
            }
            ans=max(l_ans,r_ans);
            if (a[st[now].mid]!=a[st[now].mid+1])
                ans=max(ans,l_rans+r_lans);
        }
    }
    
    void main()
    {
        scanf("%d%d",&n,&q);
        memset(a,0,sizeof(a));
        st_build(1,1,n);
        for (int i=1;i<=q;i++)
        {
            int pos,lans,rans,ans;
            scanf("%d",&pos);
            st_update(1,pos);
            st_ask(1,1,n,lans,rans,ans);
            printf("%d\n",ans);
        }
    }
}

int main()
{
    dts::main();
}

其实我很想打楼下的脸，朴素线段树。。
总耗时871ms峰值内存10.191 MiB
Accepted

状态 耗时 内存占用

#1 Accepted 2ms 324.0 KiB
#2 Accepted 39ms 3.578 MiB
#3 Accepted 105ms 9.941 MiB
#4 Accepted 116ms 10.191 MiB
#5 Accepted 3ms 332.0 KiB
#6 Accepted 109ms 7.066 MiB
#7 Accepted 138ms 7.07 MiB
#8 Accepted 135ms 9.203 MiB
#9 Accepted 112ms 7.059 MiB
#10 Accepted 108ms 7.168 MiB

#include<cstdio>
#include<algorithm>
#define m ((l+r)>>1)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int N=2e5+5;
inline int read(){
    int x=0,c=getchar();
    for(;c< '0'||c >'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())x=x*10+c-48;
    return x;
}
int n,Q,x,pre[N<<2],suf[N<<2],ans[N<<2],a[N];
void merge(int l1,int r1,int u,int l2,int r2,int v,int rt){
    if(a[r1]!=a[l2]&&pre[u]==l2-l1) pre[rt] = pre[u] + pre[v];
    else pre[rt] = pre[u];
    if(a[r1]!=a[l2]&&suf[v]==r2-r1) suf[rt] = suf[u] + suf[v];
    else suf[rt] = suf[v];
    ans[rt] = max(ans[u], ans[v]);
    if(a[r1]!=a[l2]) ans[rt] = max(ans[rt],suf[u]+pre[v]);
}
void build(int l,int r,int rt){
    if(l == r){
        ans[rt] = pre[rt] = suf[rt] = 1;return;
    }
    build(lson);
    build(rson);
    merge(lson,rson,rt);
}
void update(int p,int l,int r,int rt){
    if(l == r) {a[p]^=1;return;}
    if(p <= m) update(p,lson);
    else update(p,rson);
    merge(lson,rson,rt);
} 
int main(){
    n=read();Q=read();
    build(1,n,1);   
    while(Q--){
        update(read(),1,n,1);
        printf("%d\n",ans[1]);
    } 
}

• 测试数据 #0: Accepted, time = 15 ms, mem = 12868 KiB, score = 10
• 测试数据 #1: Accepted, time = 62 ms, mem = 12868 KiB, score = 10
• 测试数据 #2: Accepted, time = 187 ms, mem = 12868 KiB, score = 10
• 测试数据 #3: Accepted, time = 125 ms, mem = 12864 KiB, score = 10
• 测试数据 #4: Accepted, time = 15 ms, mem = 12864 KiB, score = 10
• 测试数据 #5: Accepted, time = 93 ms, mem = 12872 KiB, score = 10
• 测试数据 #6: Accepted, time = 171 ms, mem = 12864 KiB, score = 10
• 测试数据 #7: Accepted, time = 125 ms, mem = 12868 KiB, score = 10
• 测试数据 #8: Accepted, time = 125 ms, mem = 12868 KiB, score = 10
• 测试数据 #9: Accepted, time = 140 ms, mem = 12868 KiB, score = 10

Accepted, time = 1058 ms, mem = 12872 KiB, score = 100
zkw线段树+读入优化，就是这么快
```c++
#include <bits/stdc++.h>
using namespace std;

int n, m, x, N;
inline int read()
{
int a = 0, c;
do c = getchar(); while(!isdigit(c));
while(isdigit(c)) {
a = a * 10 + c - '0';
c = getchar();
}
return a;
}
void write(int i)
{
if (!i) return;
write(i/10);
putchar(i%10+'0');
}

int counta[(1<<19)+1],countl[(1<<19)+1],countr[(1<<19)+1];
int L[(1<<19)+1], R[(1<<19)+1];
int a[(1<<19)+1];

void build()
{
for (int i = n; i < n+n; i++)
L[i] = R[i] = i;
for (int i = n-1; i; i--)
L[i] = L[i<<1], R[i] = R[(i<<1)+1];
for (int i = 1; i < n+n; i++) {
a[i] = counta[i] = countl[i] = countr[i] = 0;
if (L[i] <= N+n-1)
a[i] = counta[i] = countl[i] = 1;
if (R[i] <= N+n-1)
countr[i] = 1;
}
}

void update(int i)
{
i = i+n-1;
a[i] = !a[i];
for (int j = i>>1; j; j>>=1) {
int cnt = 0, sz = R[j]-L[j]+1;
int lf = (L[j]+R[j])>>1, rf = lf+1;
if (a[lf] != a[rf]) cnt = countr[j<<1] + countl[(j<<1)+1];
counta[j] = max(cnt, max(counta[j<<1], counta[(j<<1)+1]));
countl[j] = countl[j<<1] == (sz>>1) ? max(cnt, countl[j<<1]) : countl[j<<1];
countr[j] = countr[(j<<1)+1] == (sz>>1) ? max(cnt, countr[(j<<1)+1]) : countr[(j<<1)+1];
}
}

int main()
{
N = read(); m = read();
n = (1<<18);
build();
for (int i = 1; i <= m; i++) {
x = read();
update(x);
write(counta[1]);
putchar('\n');
}
return 0;
}

链表写的线段树，重点是更新。
如果左区间的最右星星 不同于 左区间最左星星，那么这两个区间可以合并，合并后中间交错段的长度为左区间从右数的长度+右区间从左数的长度。详见代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define O 0
#define X 1
#define NEW_SPACE ((node*)malloc(sizeof(node)))

typedef struct node{
/*countL: 区间从左起保持交错的长度
countR: 区间从右起保持交错的长度
statusL: 该区间最左的元素值
statusR: 该区间最右的元素值
maxLength: 该区间保持交错的最大长度*/
struct node *left, *right;
int begin, end;
int statusL, statusR, countL, countR, maxLength;
} node;

void construct(node *root, int left, int right);
void modify(node *root, int index);
int Max(int a, int b);
int reverse(int status);

int main(){
int size, numQuery, index;
node *root;

scanf("%d %d", &size, &numQuery);
root = NEW_SPACE;
construct(root, 1, size);
for(; numQuery>0; numQuery--){
scanf("%d", &index);
modify(root, index);
printf("%d\n", root->maxLength);
}
return 0;
}
void construct(node *root, int left, int right){
int mid = (left+right)/2;
if(left>right)
return;
root->left = NULL;
root->right = NULL;
root->begin = left;
root->end = right;
root->statusL = root->statusR = O;
root->countL = root->countR = 1;
root->maxLength = 1;
if(left==right)
return;
root->left = NEW_SPACE;
root->right = NEW_SPACE;
construct(root->left, left, mid);
construct(root->right, mid+1, right);
}
void modify(node *root, int index){
int mid = (root->begin + root->end) / 2;
if(root==NULL)
return;
if(root->begin==root->end){
//change status of target
root->statusL = reverse(root->statusL);
root->statusR = root->statusL;
root->countL = root->countR = root->maxLength = 1;
return;
}
if(index<=mid)
modify(root->left, index);
else
modify(root->right, index);

root->statusL = root->left->statusL;
root->statusR = root->right->statusR;
root->countL = root->left->countL;
root->countR = root->right->countR;
root->maxLength = Max(root->left->maxLength, root->right->maxLength);
if(root->left->statusR != root->right->statusL){
//merge
root->maxLength = Max(root->maxLength, root->left->countR + root->right->countL);
if(root->left->countL == (root->left->end - root->left->begin + 1))
root->countL = root->left->countL + root->right->countL;
if(root->right->countR == (root->right->end - root->right->begin + 1))
root->countR = root->left->countR + root->right->countR;
}
}
int Max(int a, int b){
return a>b ? a:b;
}
int reverse(int status){
return status==X ? O:X;
}

测试数据 #0: Accepted, time = 0 ms, mem = 33112 KiB, score = 10

测试数据 #1: Accepted, time = 218 ms, mem = 33112 KiB, score = 10

测试数据 #2: Accepted, time = 718 ms, mem = 33116 KiB, score = 10

测试数据 #3: Accepted, time = 812 ms, mem = 33112 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 33112 KiB, score = 10

测试数据 #5: Accepted, time = 734 ms, mem = 33112 KiB, score = 10

测试数据 #6: Accepted, time = 875 ms, mem = 33116 KiB, score = 10

测试数据 #7: Accepted, time = 796 ms, mem = 33116 KiB, score = 10

测试数据 #8: Accepted, time = 843 ms, mem = 33112 KiB, score = 10

测试数据 #9: Accepted, time = 687 ms, mem = 33112 KiB, score = 10

Accepted, time = 5683 ms, mem = 33116 KiB, score = 100

终于AC了

#include <cstdio>
#include <cstring>
#include <algorithm>

#define mid (l + r) / 2
#define ls pos << 1, l, mid
#define rs pos << 1 | 1, mid + 1, r

using namespace std;

const int Rn = 199999 + 9;

int N, Q;

struct Node{
int lc, rc;
int ln, rn;
int val;
}T[Rn << 2];

void Update(int pos, int l, int r){
Node &x1 = T[pos], x2 = T[pos << 1], x3 = T[pos << 1 | 1];

x1.lc = x2.lc;
x1.rc = x3.rc;

x1.ln = x2.ln;
x1.rn = x3.rn;

x1.val = max(x2.val, x3.val);

if (x2.rc != x3.lc){
x1.val = max(x1.val, x2.rn + x3.ln);
if (x2.val == mid - l + 1){
x1.ln = x2.val + x3.ln;

}
if (x3.val == r - mid){
x1.rn = x3.val + x2.rn;
}
}
}

void Build_Tree(int pos, int l, int r){
Node &S = T[pos];
S.lc = S.rc = S.ln = S.rn = S.val = 1;
if (l == r){
return;
}
Build_Tree(ls);
Build_Tree(rs);
}

void Query(int pos, int l, int r, int x){
if (l == r){
T[pos].lc = T[pos].rc = T[pos].lc ^ 1;
return;
}
if (x <= mid){
Query(ls, x);
}
if (x > mid){
Query(rs, x);
}
Update(pos, l, r);
}

int main(){
int x;
scanf("%d %d", &N, &Q);

Build_Tree(1, 1, N);

for (int i = 0; i < Q; i ++){
scanf("%d", &x);
Query(1, 1, N, x);
printf("%d\n", T[1].val);
}
return 0;
}

代码还算简单吧，纯纯的线段树。

线段树 upddate函数写对就行了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define mmt(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define y1 fuck
#define M 1000010
using namespace std;
typedef long long LL;
typedef long double LD;
int n,q;
struct segtree
{
int lc[M],rc[M],l[M],r[M],lm0[M],rm0[M],om[M],siz,lm1[M],rm1[M];
int len(int x){return r[x]-l[x]+1;}
void upd(int x)
{
if (lm1[lc[x]]==len(lc[x]))
{
if (len(lc[x])&1) lm1[x]=lm1[lc[x]]+lm0[rc[x]];
else lm1[x]=lm1[lc[x]]+lm1[rc[x]];
}else lm1[x]=lm1[lc[x]];

if (lm0[lc[x]]==len(lc[x]))
{
if (len(lc[x])&1) lm0[x]=lm0[lc[x]]+lm1[rc[x]];
else lm0[x]=lm0[lc[x]]+lm0[rc[x]];
}else lm0[x]=lm0[lc[x]];

if (rm1[rc[x]]==len(rc[x]))
{
if (len(rc[x])&1) rm1[x]=rm1[rc[x]]+rm0[lc[x]];
else rm1[x]=rm1[rc[x]]+rm1[lc[x]];
}else rm1[x]=rm1[rc[x]];

if (rm0[rc[x]]==len(rc[x]))
{
if (len(rc[x])&1) rm0[x]=rm0[rc[x]]+rm1[lc[x]];
else rm0[x]=rm0[rc[x]]+rm0[lc[x]];
}else rm0[x]=rm0[rc[x]];

om[x]=max( max( max( om[lc[x]],om[rc[x]]),rm0[lc[x]]+lm1[rc[x]]),rm1[lc[x]]+lm0[rc[x]]);
}
void build(int x,int L,int R)
{
l[x]=L;r[x]=R;
if (L==R) {lm1[x]=rm1[x]=1;om[x]=lm0[x]=rm0[x]=0;return;}
int mi=(L+R)>>1;
build(lc[x]=++siz,L,mi);build(rc[x]=++siz,mi+1,R);
upd(x);
}
void modify(int x,int p)
{
if (l[x]==r[x])
{
if (lm1[x]==1) {lm1[x]=rm1[x]=0;lm0[x]=rm0[x]=1;}
else {lm1[x]=rm1[x]=1;lm0[x]=rm0[x]=0;}
return;
}
int mi=(l[x]+r[x])>>1;
if (p<=mi) modify(lc[x],p);
else modify(rc[x],p);
upd(x);
}
}Tree;
int main()
{
Tree.siz=1;
scanf("%d%d",&n,&q);
Tree.build(1,1,n);
int t,i;
FOR(i,1,q)
{
scanf("%d",&t);
Tree.modify(1,t);
printf("%d\n",Tree.om[1]);
}
return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <utility>
#define N 200005
using namespace std;
typedef long long LL;
int n, q;
struct node
{
int l, r, maxl[2][2], len;
}tree[N * 4];
void init()
{
//freopen("1.in", "r", stdin);
scanf("%d%d", &n, &q);
}
void build_tree(int th, int l1, int r1)
{
tree[th].l = l1;
tree[th].r = r1;
tree[th].maxl[0][0] = tree[th].maxl[1][0] = 1;
tree[th].maxl[0][1] = tree[th].maxl[1][1] = 0;
tree[th].len = 1;
if(l1 == r1)
return;
int mid = (l1 + r1) / 2;
build_tree(2 * th, l1, mid);
build_tree(2 * th + 1, mid + 1, r1);
}
void change(int pos, int th)
{
if(tree[th].l == tree[th].r)
{
tree[th].maxl[0][0] = tree[th].maxl[1][0] = 1 - tree[th].maxl[0][0];
tree[th].maxl[0][1] = tree[th].maxl[1][1] = 1 - tree[th].maxl[0][1];
return;
}
int mid = (tree[th].l + tree[th].r) / 2;
if(pos <= mid)
change(pos, 2 * th);
else
change(pos, 2 * th + 1);
int len1 = mid - tree[th].l + 1, len2 = tree[th].r - mid;
tree[th].maxl[0][0] = tree[2 * th].maxl[0][0];
if(tree[th].maxl[0][0] == len1)
tree[th].maxl[0][0] += tree[2 * th + 1].maxl[0][len1 & 1];
tree[th].maxl[0][1] = tree[2 * th].maxl[0][1];
if(tree[th].maxl[0][1] == len1)
tree[th].maxl[0][1] += tree[2 * th + 1].maxl[0][(len1 + 1) & 1];
tree[th].maxl[1][0] = tree[2 * th + 1].maxl[1][0];
if(tree[th].maxl[1][0] == len2)
tree[th].maxl[1][0] += tree[2 * th].maxl[1][len2 & 1];
tree[th].maxl[1][1] = tree[2 * th + 1].maxl[1][1];
if(tree[th].maxl[1][1] == len2)
tree[th].maxl[1][1] += tree[2 * th].maxl[1][(len2 + 1) & 1];
tree[th].len = max(tree[2 * th].len, tree[2 * th + 1].len);
int tmp = max(tree[2 * th].maxl[1][0] + tree[2 * th + 1].maxl[0][1], tree[2 * th].maxl[1][1] + tree[2 * th + 1].maxl[0][0]);
tree[th].len = max(tree[th].len, tmp);
}
void deal()
{
build_tree(1, 1, n);
for(int i = 1; i <= q; ++i)
{
int tmp;
scanf("%d", &tmp);
change(tmp, 1);
printf("%d\n", tree[1].len);
}
}
int main()
{
init();
deal();
return 0;
}

-------------以上线段树算法来自1756500824，orz orz--------------------------------

楼下dbg莫嚣张， 贴别人代码算神马233;
线段树裸过， 只要维护左右端点颜色和长度， 然后用左右儿子维护自己即可。
下面是我的change函数：
void change(int p, int l, int r)
{
if (t[p].l == l && t[p].r == r)
{
t[p].lc = t[p].rc = 1 - t[p].lc;
return;
}
int mid = (t[p].l+t[p].r) >> 1;
int L = p << 1, R = p << 1 | 1;
if (r <= mid) change(L, l, r);
if (l > mid) change(R, l, r);
t[p].lc = t[L].lc;
t[p].rc = t[R].rc;
t[p].maxs = max(t[L].maxs, t[R].maxs);
t[p].ll = t[L].ll;
t[p].rl = t[R].rl;
if (t[L].rc != t[R].lc)
{
t[p].maxs = max(t[p].maxs, t[L].rl + t[R].ll);
if (t[L].maxs == t[L].len) t[p].ll = t[L].len + t[R].ll;
if (t[R].maxs == t[R].len) t[p].rl = t[R].len + t[L].rl;
}
}