P7912

标签：输出量 P7912 复杂度 global 同阶 import os

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

---

先摆复杂度：均摊 \(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()

标签：输出量,P7912,复杂度,global,同阶,import,os
From： https://www.cnblogs.com/myee/p/Luogu7912.html