数据结构模板

# head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
N = 1000
head, e, ne, idx = -1, [0] * N, [0] * N, 0

# 头插法插入a
def insert(a:int):
    global head,idx
    e[idx] = a
    ne[idx] = head
    head = idx
    idx += 1

# 将头结点删除，需要保证头结点存在
def remove():
    global head
    head = ne[head]

# e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
N = 1000
e, l, r, idx = [0] * N, [0] * N, [0] * N, 0

# 初始化
def init():
    global idx
    # 0是左端点，1是右端点
    r[0] = 1 
    l[1] = 0
    idx = 2

# 在节点a的右边插入一个数x
def insert(a:int, x:int):
    global idx
    e[idx] = x
    l[idx] = a
    r[idx] = r[a]
    l[r[a]] = idx
    r[a] = idx
    idx += 1

# 删除节点a
def remove(a:int):
    l[r[a]] = l[a]
    r[l[a]] = r[a]

# tt表示栈顶
N = 1000
stk, tt = [0] * N, 0

# 向栈顶插入一个数
def push(x:int):
    global tt
    tt += 1
    stk[tt] = x

# 从栈顶弹出一个数
def pop():
    global tt
    stk[tt]
    tt -= 1

# 查看栈顶元素
def top():
    return stk[tt]

# 判断栈是否为空，如果 tt > 0，则表示不为空
def isEmpty():
    return tt <= 0

# hh 表示队头，tt表示队尾
N = 1000
q, hh, tt = [0] * N, 0, -1

# 向队尾插入一个数
def push(x:int):
    global tt
    tt += 1
    q[tt] = x

# 从队头弹出一个数
def pop():
    global hh
    ans = q[hh]
    hh += 1
    return ans

# 查看队头元素
def front():
    return q[hh]

# 查看队尾元素
def back():
    return q[tt]

# 判断队列是否为空，如果 hh <= tt，则表示不为空
def isEmpty():
    return hh > tt

# hh 表示队头，tt表示队尾的后一个位置
N = 1000
q, hh, tt = [0] * N, 0, 0

# 向队尾插入一个数
def push(x:int):
    global tt
    q[tt] = x
    tt += 1
    if tt == N: 
        tt = 0

# 从队头弹出一个数
def pop():
    global hh
    ans = q[hh]
    hh += 1
    if hh == N:
        hh = 0

# 查看队头的值
def front():
    return q[hh]

# 判断队列是否为空，如果hh != tt，则表示不为空
def isEmpty():
    return hh == tt

N = 1000
stk, tt = [0] * N, 0
for i in range(1,n+1):
    while tt and check(stk[tt], i):
        tt -= 1
    tt += 1
    stk[tt] = i

N = 1000
q, hh, tt = [0] * N, 0, -1
for i in range(n):
    while hh <= tt and check_out(q[hh]):
        hh += 1  # 判断队头是否滑出窗口
    while hh <= tt and check(q[tt], i):
        tt -= 1
    tt += 1
    q[tt] = i

# s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
# 求模式串的Next数组：
ne = [0] * N
i, j = 2, 0
while i <= m:
    while j and p[i] != p[j + 1]:
        j = ne[j];
    if p[i] == p[j + 1]:
        j += 1
    ne[i] = j
    i += 1

# 匹配
i, j = 1, 0
while i <= n:
    while j and s[i] != p[j + 1]:
        j = ne[j]
    if s[i] == p[j + 1]:
        j += 1
    if j == m:
        j = ne[j]
        # 匹配成功后的逻辑

N = 1000
son, cnt, idx = [[0] * 26 for i in range(N)], [0] * N, 0
# 0号点既是根节点，又是空节点
# son[][]存储树中每个节点的子节点
# cnt[]存储以每个节点结尾的单词数量

# 插入一个字符串
def insert(str):
    p = 0
    for i in range(len(str)):
        u = ord(str[i]) - ord('a')
        if not son[p][u]:
            idx += 1
            son[p][u] = idx
        p = son[p][u]
    cnt[p] += 1

# 查询字符串出现的次数
def query(str):
    p = 0
    for i in range(len(str)):
        u = ord(str[i]) - ord('a')
        if not son[p][u]:
            return 0
        p = son[p][u]
    return cnt[p]

N = 1000
p = list(range(N)) #存储每个点的祖宗节点

# 返回x的祖宗节点
def find(x:int):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

# 合并a和b所在的两个集合：
p[find(a)] = find(b)

N = 1000
p, size = list(range(N)), [1] * N
# p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

# 返回x的祖宗节点
def find(x:int):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

# 合并a和b所在的两个集合：
size[find(b)] += size[find(a)]
p[find(a)] = find(b)

N = 1000
p, d = list(range(N)), [0] * N
# p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

# 返回x的祖宗节点
def find(x:int):
    if p[x] != x:
        u = find(p[x])
        d[x] += d[p[x]]
        p[x] = u
    return p[x]

# 合并a和b所在的两个集合：
p[find(a)] = find(b)
d[find(a)] = distance; # 根据具体问题，初始化find(a)的偏移量

N, M = 1000, 100
e, w, ne, h, cnt, = [0] * N, [0] * N, [0] * N, [-1] * M, 0

def add(a:int,b:int,c:int):
    global cnt
    e[cnt] = b
    w[cnt] = c
    ne[cnt] = h[a]
    h[a] = cnt
    cnt += 1