题解P6492 [COCI2010-2011#6] STEP

暗ざ之殇 · 2020-06-20 20:21:42 · 题解

题解

首先题目中的 L 和 R 我们可以分别用 0 和 1来代替；

一个很自然的想法是用线段树维护答案区间的左右端点；

思路简单暴力，但是合并信息的时候需要考虑的情况较多，且复杂度较高，会TLE；

巧妙的思路

先介绍一下代码里的数组：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=8e5+5;
int n,m;
int S[N],H[N],L[N],R[N],len[N],ans[N];
void work(int node,int k)                   //将node节点的值赋值为k,并更新一下该点信息 
{
    ans[node]=S[node]=H[node]=1;
    L[node]=R[node]=k;
}
void pushup(int node)
{
    if(R[node<<1]^L[node<<1|1])             //如果左区间的右端点和右区间的左端点不同 
    {
        ans[node]=H[node<<1]+S[node<<1|1];  //考虑两端合并后的符合条件的区间长度 
        ans[node]=max(ans[node],ans[node<<1]);  //与左区间的进行比较 
        ans[node]=max(ans[node],ans[node<<1|1]);//与右区间的进行比较 
    }
    else ans[node]=max(ans[node<<1],ans[node<<1|1]);  //否则只用考虑左右区间中最长的区间 
    L[node]=L[node<<1];R[node]=R[node<<1|1];//L和R数组的维护显而易见   
    if(S[node<<1]==len[node<<1]&&R[node<<1]^L[node<<1|1]) S[node]=S[node<<1]+S[node<<1|1];  //左区间的S包含整个区间并且左区间的右端点与右区间的左端点不同,则两个区间的S合并成大区间的S 
    else S[node]=S[node<<1];                //否则就继承左区间的S             
    if(H[node<<1|1]==len[node<<1|1]&&R[node<<1]^L[node<<1|1]) H[node]=H[node<<1|1]+H[node<<1]; //右区间的H包含整个区间并且左区间的右端点与右区间的左端点不同,则两个区间的H合并成大区间的H 
    else H[node]=H[node<<1|1];              //否则就继承右区间的H 
}
void build(int node,int l,int r)            
{
    len[node]=r-l+1;                        //区间长度 
    if(l==r)                                //递归到了叶子节点 
    {
        work(node,0);                       //将该点赋值0,并更新一下该点信息 
        return ;
    }
    int mid=(l+r)/2;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    pushup(node);
}
void change(int node,int l,int r,int x)
{
    if(l==r)                                //递归到了叶子节点 
    {
        work(node,!L[node]);                //将该节点赋值为!L[node],从而达到0变成1,1变成0的效果 
        return ;
    }
    int mid=(l+r)/2;
    if(x<=mid) change(node<<1,l,mid,x);
    else change(node<<1|1,mid+1,r,x);
    pushup(node);
}
int main()
{
    scanf("%d %d",&n,&m);
    build(1,1,n);                           //建树     
    for(int i=1;i<=m;i++)
    {
        int x;
        scanf("%d",&x);
        change(1,1,n,x);                    //单点修改 
        printf("%d\n",ans[1]);              //每次要输出最长的符合条件的区间 
    }
    return 0;
}