Jennie

区间最长子序列的变体罢了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
struct t{
    int ls;
    int rs;
    int l;int r;
    int ans;
    int len;
    int val;
}tr[4000005];
int n;
int q;
void update(int ro){
    if(tr[ro<<1].rs!=tr[ro<<1|1].ls){
        tr[ro].ans=max(tr[ro<<1].ans,max(tr[ro<<1|1].ans,tr[ro<<1].r+tr[ro<<1|1].l));
    }else{
        tr[ro].ans=max(tr[ro<<1].ans,tr[ro<<1|1].ans);
    }
    if(tr[ro<<1].ans==tr[ro<<1].len&&tr[ro<<1].rs!=tr[ro<<1|1].ls){
        tr[ro].l=tr[ro<<1].len+tr[ro<<1|1].l;
    }else{
        tr[ro].l=tr[ro<<1].l;
    }
    if(tr[ro<<1|1].ans==tr[ro<<1|1].len&&tr[ro<<1].rs!=tr[ro<<1|1].ls){
        tr[ro].r=tr[ro<<1|1].len+tr[ro<<1].r;
    }else{
        tr[ro].r=tr[ro<<1|1].r;
    }
    tr[ro].ls=tr[ro<<1].ls;tr[ro].rs=tr[ro<<1|1].rs;
}
void build(int ro,int l,int r){
    if(l==r){
        tr[ro].ls=tr[ro].rs=0;
        tr[ro].l=1;
        tr[ro].r=1;
        tr[ro].ans=1;
        tr[ro].val=0;
        tr[ro].len=1;
        return ;
    }
    int mid=(l+r)>>1;
    tr[ro].len=r-l+1;
    build(ro<<1,l,mid);
    build(ro<<1|1,mid+1,r);
    update(ro);
}

void change(int ro,int l,int r,int L,int R){
    if(l==r){
        tr[ro].val=!tr[ro].val;
        tr[ro].ls=tr[ro].val;
        tr[ro].rs=tr[ro].val;
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid) change(ro<<1,l,mid,L,R);
    else change(ro<<1|1,mid+1,r,L,R);
    update(ro);
    //printf("%d %d %d %d %d\n",ro,l,r,tr[ro].ans,tr[ro].l);
    return ;
}
int x;
int main(){
    read(n);read(q);
    build(1,1,n);
    for(int i=1;i<=q;++i){
        read(x);
        change(1,1,n,x,x);
        printf("%d\n",tr[1].ans);
    }
    return 0;
}