这道题为啥不可以直接维护。。。。
#include<bits/stdc++.h>
using namespace std;
#define N 11400000
struct node{
int l,r,Lmax,Rmax,tot,L,R;
}t[N];
int read()
{
int x=0,f=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
void update(int x)
{
if(t[x<<1].R != t[x<<1|1].L) t[x].tot = t[x<<1].Rmax + t[x<<1|1].Lmax;
t[x].tot = max(max(t[x<<1].tot,t[x<<1|1].tot),t[x].tot);
t[x].L = t[x<<1].L;
t[x].R = t[x<<1|1].R;
if(t[x<<1].R != t[x<<1|1].L && t[x<<1].Lmax == t[x<<1].r-t[x<<1].l+1)
t[x].Lmax = t[x<<1].tot + t[x<<1|1].Lmax;
else t[x].Lmax = t[x<<1].Lmax;
if(t[x<<1].R != t[x<<1|1].L && t[x<<1|1].Rmax == t[x<<1|1].r-t[x<<1|1].l+1)
t[x].Rmax = t[x<<1].Rmax + t[x<<1|1].tot;
else t[x].Rmax = t[x<<1|1].Rmax;
t[x].tot = max(t[x].Lmax,max(t[x].Rmax,t[x].tot));
}
void build(int q,int l,int r)
{
t[q].l = l;t[q].r = r;
if(l == r)
{
t[q].Lmax=t[q].Rmax=t[q].tot=t[q].L=t[q].R=1;
return ;
}
int mid = l + r>>1;
build(q<<1,l,mid);
build(q<<1|1,mid+1,r);
update(q);
}
void change(int q,int l,int r,int key)
{
if(key == l && key == r)
{
t[q].R = t[q].L = t[q].L^1;
return;
}
int mid = l+r>>1;
if(key <= mid) change(q<<1,l,mid,key);
if(key > mid) change(q<<1|1,mid+1,r,key);
update(q);
}
int n,m;
signed main()
{
n=read();m=read();
build(1,1,n);
for(int i = 1;i <= m;i++)
{
int a = read();
change(1,1,n,a);
printf("%d\n",t[1].tot);
}
}