841字符串哈希

1、储存p是为了下面方便getHash
2、在gethash时，要把s[l-1]与s[r]相差的位数补上去。

n,m = map(int,input().split())
string = ' '+ str(input())
N = 100010
P,Q = 131,2**64
p = [0]*N
s = [0]*N

p[0] = 1
for i in range(1,n+1):
# 储存p是为了下面gethash好计算
 p[i] = p[i-1]*P%Q
 s[i] = (s[i-1]*P+ord(string[i]))%Q

def getHash(l,r):
    # 把相差的位数补上去
    return (s[r]-s[l-1]*p[r-l+1])%Q
        
for _ in range(m):
    l1,r1,l2,r2 = map(int, input().split())
    x1 = getHash(l1,r1)
    x2 = getHash(l2,r2)
    if x1==x2:
        print('Yes')
    else:
        print('No')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

838堆排序

基本忘了

n,m = map(int,input().split())
# nums = list(map(int,input().split()))
N = 100010
h = [0] + [int(x) for x in input().split()]

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

for i in range(int(n/2), 0, -1):
    down(i)

for _ in range(m):
    print(h[1], end=' ')
    h[1],h[n]=h[n],h[1]
    n -= 1
    down(1)
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

839模拟堆

1、插入后，要进行up
2、up函数中，要不断改变u的值
3、down函数中，交换完后，要继续递归down，看看下面的层是否能交换。

n = int(input())
idx,size = 0,0
N = 100010
ph,hp,h = [0]*N, [0]*N, [0]*N

def insert(x):
    global idx,size
    idx+=1
    size+=1
    ph[idx] = size
    hp[size] = idx
    h[size] = x
    # 插入后要排序
    up(size)

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 t!=u:
        swap(t,u)
        # 交换完要继续down，有可能还能下
        down(t)
def up(u):
    while u//2 and h[u//2]>h[u]:
        swap(u//2,u)
        # 要不断改变u的值
        u //=2
        
def swap(a,b):
    ph[hp[a]],ph[hp[b]] = b,a
    hp[a],hp[b] = hp[b],hp[a]
    h[a],h[b] = h[b],h[a]

for _ in range(n):
    op,*pt = input().split()
    if op=='I':
        x = int(pt[0])
        insert(x)
    elif op=='PM':
        print(h[1])
    elif op=='DM':
        swap(1,size)
        size -= 1
        down(1)
    elif op=='D':
        k = int(pt[0])
        k = ph[k]
        swap(size,k)
        size -= 1
        down(k)
        up(k)
    else:
        k,x = map(int, pt)
        k = ph[k]
        h[k] = x
        up(k)
        down(k)
        
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62