洛谷p6492[COCI2010-2011#6] STEP

题目描述

给定一个长度为 nn 的字符序列 aa，初始时序列中全部都是字符 L。

有 qq 次修改，每次给定一个 xx，若 a_xax​ 为 L，则将 a_xax​ 修改成 R，否则将 a_xax​ 修改成 L。

对于一个只含字符 L，R 的字符串 ss，若其中不存在连续的 L 和 R，则称 ss 满足要求。

每次修改后，请输出当前序列 aa 中最长的满足要求的连续子串的长度。

输入格式

第一行有两个整数，分别表示序列的长度 nn 和修改操作的次数 qq。

接下来 qq 行，每行一个整数，表示本次修改的位置 xx。

输出格式

对于每次修改操作，输出一行一个整数表示修改 aa 中最长的满足要求的子串的长度。

输入输出样例

输入 #1复制

6 2
2
4

输出 #1复制

3
5

输入 #2复制

6 5
4
1
1
2
6

输出 #2复制

3
3
3
5
6

说明/提示

数据规模与约定

对于全部的测试点，保证 1 leq n, q leq 2 imes 10^51≤n,q≤2×105，1 leq x leq n1≤x≤n。

说明

题目译自 COCI2010-2011 CONTEST #6 T5 STEP，翻译来自 @一扶苏一。

 这道题本质就是一个线段树，所以我们改一改代码就行了

#include<cstdio>
#include<iostream>

using namespace std;
typedef long long int ll;

const int maxn=200005;

int n,q;
int a[maxn];

ll maxx(const ll x,const ll y,const ll z)
{
    return max(max(x,y),z);
}


struct Node
{
    int l,r;
    int lv,rv,vv;
    Node *ls,*rs;
    
    inline void pushup()
    {
        lv=ls->lv;
        rv=rs->rv;
        vv=maxx(0,ls->vv,rs->vv);
        if(a[ls->r]!=a[rs->l])
        {
            vv=max(vv,ls->rv+rs->lv);
            if(ls->l+ls->lv-1==ls->r)
            {
                lv+=rs->lv;
            }
            if(rs->l+rs->lv-1==rs->r)
            {
                rv+=ls->rv;
            }
        }
    }
    
    void upd(const int x)
    {
        if(l==r) return;
        if(ls->r >= x)
        {
            ls->upd(x);
        }
        else
        {
            rs->upd(x);
        }
        pushup();
    }
};

Node Mem[maxn<<1],*pool=Mem;
Node *New(const int l,const int r)
{
    Node *u=pool++;
    u->l=l;u->r=r;
    if(l!=r)
    {
        int m=(l+r)>>1;
        u->ls=New(l,m);
        u->rs=New(m+1,r);
        u->pushup();
    }
    else
    {
        u->lv=u->rv=u->vv=1;
    }
    return u;
}

int main()
{
    scanf("%d%d",&n,&q);
    Node *rot=New(1,n);
    for(int x;q;--q)
    {
        scanf("%d",&x);
        a[x]^=1;
        rot->upd(x);
        printf("%d
",rot->vv);
    }
}