题解
单点修改线段树,向上更新,再注意下转移方程就行了
code
#include<bits/stdc++.h>
using namespace std;
int tree[800005]={0};
int len[800005][2][2]={0};//代表第几个节点,0/1在左/右边的最大有效长度
int a[200005];
void pushup(int node,int l,int r,int mid)
{
tree[node]=max(max(tree[node*2],tree[node*2+1]),max(len[node*2][1][1]+len[node*2+1][0][0],len[node*2][0][1]+len[node*2+1][1][0]));
len[node][0][0]=len[node*2][0][0];
len[node][1][0]=len[node*2][1][0];
len[node][0][1]=len[node*2+1][0][1];
len[node][1][1]=len[node*2+1][1][1];
if(len[node*2][0][0]==mid-l+1)len[node][0][0]+=len[node*2+1][1-a[mid]][0];
if(len[node*2][1][0]==mid-l+1)len[node][1][0]+=len[node*2+1][1-a[mid]][0];
if(len[node*2+1][0][1]==r-mid)len[node][0][1]+=len[node*2][1-a[mid+1]][1];
if(len[node*2+1][1][1]==r-mid)len[node][1][1]+=len[node*2][1-a[mid+1]][1];
}
void build(int node,int l,int r)
{
if(l==r)
{
a[l]=0;
tree[node]=1;
len[node][0][0]=1;
len[node][0][1]=1;
//printf("%d:%d\n",node,tree[node]);
return;
}
int mid=(l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
pushup(node,l,r,mid);
// printf("%d:%d\n",node,tree[node]);
}
void update(int node,int l,int r,int x)
{
if(l==r&&r==x)
{
len[node][a[r]][1]=0;
len[node][a[r]][0]=0;
a[r]^=1;
len[node][a[r]][1]=1;
len[node][a[l]][0]=1;
return;
}
int mid=(l+r)/2;
if(x<=mid) update(node*2,l,mid,x);
else update(node*2+1,mid+1,r,x);
pushup(node,l,r,mid);
}
int main()
{
int n,q;
cin>>n>>q;
build(1,1,n);
while(q--)
{
int x;
cin>>x;
update(1,1,n,x);
cout<<tree[1]<<endl;
//for(int i=1;i<=n;i++) cout<<a[i]<<" ";
// cout<<endl<<endl;
}
//for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}
标签:node,int,tree,mid,len,STEP,build,P6492,2011
From: https://www.cnblogs.com/pure4knowledge/p/18034571