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

概述　　题意：给定一个串只有01 一开始全部都是0 每次 *** 作将x位置的数取反问最长序列满足相邻数字不同区间合并线段树再记录一下区间最左端的数字和最右端的数字即可 #include<bits/stdc++.h>using namespace std;//input by bxd#define rep(i,a,b) for(int i=(a);

　　题意：给定一个串只有01 一开始全部都是0 每次 *** 作将x位置的数取反问最长序列满足相邻数字不同

区间合并线段树再记录一下区间最左端的数字和最右端的数字即可

#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,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|1voID 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 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,1);        cout<<maxans[1]<<endl;    }    return 0;}