P2253 好一个一中腰鼓！ 线段树

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<‘=‘<<(x)<<endl)
#define pb push_back
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
typedef pair<int,int>pii;
//////////////////////////////////
const int N=2e6+10;

int maxans[N<<2],lmax[N<<2],rmax[N<<2],le[N<<2],ri[N<<2],len[N<<2];
#define lson l,m,pos<<1
#define rson m+1,r,pos<<1|1

void up(int pos)
{
    le[pos]=le[pos<<1];
    ri[pos]=ri[pos<<1|1];
    lmax[pos]=lmax[pos<<1];
    rmax[pos]=rmax[pos<<1|1];
    maxans[pos]=max(maxans[pos<<1],maxans[pos<<1|1]);
    if(ri[pos<<1]!=le[pos<<1|1])
    {
        maxans[pos]=max(maxans[pos],rmax[pos<<1]+lmax[pos<<1|1]);
        if(len[pos<<1]==lmax[pos<<1])
        lmax[pos]=len[pos<<1]+lmax[pos<<1|1];
        if(len[pos<<1|1]==rmax[pos<<1|1])
        rmax[pos]=len[pos<<1|1]+rmax[pos<<1];
    }
}

void build(int l,int r,int pos)
{
    len[pos]=r-l+1;
    if(l==r){maxans[pos]=lmax[pos]=rmax[pos]=1;le[pos]=ri[pos]=0;return ;}
    int m=(l+r)>>1;
    build(lson);build(rson);up(pos);
}

void upnode(int x,int l,int r,int pos)
{
    if(l==r){le[pos]=ri[pos]=(ri[pos]+1)%2;return ;}
    int m=(l+r)>>1;
    if(x<=m)upnode(x,lson);
    else upnode(x,rson);
    up(pos);
}

int main()
{
    int n,m;
    cin>>n>>m;
    build(1,n,1);
    while(m--)
    {
        int x;cin>>x;
        upnode(x,1,n,1);
        cout<<maxans[1]<<endl;
    }
    return 0;
}