题目描述

blablabla

样例

N = int(str(input()))
n = 100010


h = [0 for i in range(n+1)]
ph = [0 for i in range(n+1)]
hp = [0 for i in range(n+1)]


size = 0

def heapswap(a, b):
    ph[ hp[a] ], ph[ hp[b] ] = ph[ hp[b] ], ph[ hp[a] ]
    hp[a], hp[b] = hp[b], hp[a]
    h[a], h[b] = h[b], h[a]

def down(u):
    t = u
    if u*2 <= size and h[u*2] < h[t]:t = u*2
    if u*2+1 <= size and h[u*2+1] < h[t]:t = u*2+1
    if u != t:
        heapswap(u, t)
        down(t)

def up(u):
    while u//2 and h[u//2] > h[u]:
        heapswap(u//2, u)
        u = u//2

if __name__ == "__main__":
    M = 0
    while N:
        N -= 1
        line = list(input().split())
        opt = line[0]
        if opt == 'I':
            v = int(line[1])
            size += 1
            M += 1
            ph[M] = size
            hp[size] = M
            h[size] = v
            up(size)
        elif opt == 'PM':
            print(h[1])
        elif opt == 'DM':
            heapswap(1,size)
            size -= 1
            down(1)
        elif opt == 'D':
            k = int(line[1])
            k = ph[k]
            heapswap(k, size)
            size -= 1
            down(k),
            up(k)
        elif opt == 'C':
            k = int(line[1])
            x = int(line[2])
            k = ph[k]
            h[k] = x
            down(k)
            up(k)




N = int(str(input()))
n = 100010

h = [0 for i in range(n)]
hp = [0 for i in range(n)]
ph = [0 for i in range(n)]
size = 0

def heapswap(a, b):
    ph[hp[a]], ph[hp[b]] = ph[hp[b]], ph[hp[a]]
    hp[a], hp[b] = hp[b], hp[a]
    h[a], h[b] = h[b], h[a]

def down(u):
    t = u
    if 2*u <= size and h[2*u] < h[t]: t = 2*u
    if 2*u + 1 <= size and h[2*u+1] < h[t]:t = 2*u + 1
    if u != t:
        heapswap(u, t)
        down(t)

def up(u):
    while u // 2 and h[u//2] > h[u]:
        heapswap(u//2, u)
        u = u //2

if __name__ == "__main__":
    M = 0
    while N:
        N -= 1
        line = list(input().split())
        opt = line[0]

        if opt == 'I':
            V = int(line[1])
            size += 1
            M += 1
            h[size] = V
            hp[size] = M
            ph[M] = size
            up(size)
        elif opt == 'PM':print(h[1])
        elif opt == 'DM':
            heapswap(1, size)
            size -= 1
            down(1)
        elif opt == 'D':
            k = int(line[1])
            nk = ph[k]
            heapswap(nk, size)
            size -= 1
            down(nk)
            up(nk)
        elif opt == 'C':
            k,x = int(line[1]), int(line[2])
            nk = ph[k]
            h[nk] = x
            down(nk)
            up(nk)

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla