无题目传送门

大致题意:

有一初始为$0$,长度为$n$的序列。$q$次操作反转单点(01互换)。每次操作后求最长的$01$间隔排列的子段长度。

$1\leq n,q \leq 200000$


Solution

直接求$01$的序列长是比较困难的(指蒟蒻用珂朵莉疯狂TLE),所以考虑转化。

因为是$01$间隔的,所以把它们每相邻两个异或起来就会得到一个全$1$且长度小$1$的序列。

比如$010100$就会变成$11110$。

由于是单点修改,所以每次仅会影响对应异或序列中的前后元素。

所以可以方便地把问题转化为,维护一个长度为$n-1$的序列,每次对$x$的操作改为对$x$和$x+1$的取反(如果不为$1$和$n$)。这在原序列中表示的是$(x,x-1)$与$(x,x+1)$的异或值。

然后最后的问题就是解决在这样一个序列中求最长的连续$1$的个数了。

由于是动态的,维护序列自然想到线段树。最长连续$1$的个数可以换一个思维,也就是不含0的最大子段和

那么怎么做到不含0呢?只需要让我们求最大子段和取不到0就行了。那么把原有的0都换成极小值,再用线段树维护一个区间子段和就可以了。

简单说下求区间子段和。

一个线段树节点维护四个信息:$l,r,v,s$,分别表示以左端点开头的最大子段和,以右端点结束的最大子段和,节点内最大子段和,节点内权值和

每次都是单点修改,那么修改后的节点$k$四个参数分别应该为0,0,0,-INF(修改为负值)或1,1,1,1(修改为正值)。

核心:

t[k].s=t[ls].s+t[rs].s;
t[k].l=max(t[ls].l,t[ls].s+t[rs].l);
t[k].r=max(t[rs].r,t[rs].s+t[ls].r);
t[k].v=max(max(t[ls].v,t[rs].v),t[ls].r+t[rs].l);

从左端点开头的最大子段和,要么是他左儿子的最大子段和,要么是他左儿子的权值和再加上右儿子从左端开始的最大子段和。这样是两种保证子段连续的情况。右端点结尾的同理。

整体的最大子段和要么是左/右儿子的最大子段和,要不是左右儿子各出自己的右部分和左部分拼在一起。

于是就完了


code:

#include<bits/stdc++.h>
#define int long long
#define N 200020
#define INF 0x3f3f3f3f
#define ls (k<<1)
#define rs (k<<1|1)
using namespace std;
struct node
{
    int l,r,v,s;
}t[N<<2];
int val[N];
void work(int k,int l,int r,int p,int c)
{
    if(l==r)
    {
        if(c==1)t[k]=(node){1,1,1,1};
        else t[k]=(node){0,0,0,c};
        return;
    }
    int m=l+r>>1;
    if(p<=m)work(ls,l,m,p,c);
    else work(rs,m+1,r,p,c);
    t[k].s=t[ls].s+t[rs].s;
    t[k].l=max(t[ls].l,t[ls].s+t[rs].l);
    t[k].r=max(t[rs].r,t[rs].s+t[ls].r);
    t[k].v=max(max(t[ls].v,t[rs].v),t[ls].r+t[rs].l);
}
void build(int l,int r,int k)
{
    if(l==r)
    {
        t[k].s=-INF;
        return;
    }
    int m=l+r>>1;
    build(l,m,ls);
    build(m+1,r,rs);
    t[k].s=t[ls].s+t[rs].s;
}
signed main()
{
    int n,m,x;
    scanf("%lld%lld",&n,&m);
    build(1,n,1);
    while(m--)
    {
        scanf("%lld",&x);
        val[x]=(!val[x]);
        if(x!=1)work(1,1,n,x  ,val[x]^val[x-1]?1:-INF);
        if(x!=n)work(1,1,n,x+1,val[x]^val[x+1]?1:-INF);
        printf("%lld\n",t[1].v+1);
    }
}
最后修改:2020 年 08 月 27 日 08 : 50 PM