Luogu7912

初中同学问我咋做，所以就写了一份题解。

先摆复杂度：均摊 \(O(n)\)。

考虑，如果我们每次操作的复杂度都与输出量同阶，而输出量总量 \(O(n)\)，则复杂度得到均摊。

于是我们现在要设计一个算法，满足每步复杂度与输出量同阶。

考虑暴力维护当前的每个颜色段开头元素，以及在当前总序列中每个元素的前驱、后继。

这个通过一个链表即可实现。

容易分析出每步复杂度与输出量同阶。

于是本题解完。

以下是参考代码（常数很大，已经过卡常）：

import io

import os

import sys

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

a=[]

b=0

def readInt():

    global input

    global a

    global b

    if len(a)<=b:

        a=list(map(int,input().split()));b=0

    ans=a[b];b+=1

    return ans

n=readInt();S=[];now=[];nxt=[];pre=[];done=[]

for i in range(n):

    S.append(readInt());now.append(i);nxt.append(i+1);pre.append(i-1);done.append(False)

def Merge():

    global S

    global now

    global done

    x=[]

    m=len(now)

    for i in range(m):

        if not done[now[i]] and (not len(x) or S[x[-1]] != S[now[i]]):

            x.append(now[i])

    now=x

def Pop():

    global S

    global now

    global nxt

    global pre

    global done

    m=len(now)

    if m:

        for i in range(m-1):

            sys.stdout.write(str(now[i]+1)+' ')

    sys.stdout.write(str(now[-1]+1)+'\n')

    x=[]

    for i in range(m):

        p=now[i]

        done[p]=True

        if pre[p] != -1:

            nxt[pre[p]]=nxt[p]

        if nxt[p] != n:

            pre[nxt[p]]=pre[p]

            if S[nxt[p]] == S[p] and (not len(x) or S[x[-1]] != S[now[i]]):

                x.append(nxt[p])

    now=x

Merge()

while len(now):

    Pop()

巴特西

Luogu7912

最新文章

热门文章