如下 AcWing 3115.疯狂的馒头空间复杂度超了——如何优化

"""
并查集
p[i]的含义是第i个元素后面第一个没有被覆盖的左端点
因此可以从后往前推，得到区间的左端点和右端点
然后找到这个左端点后面第一个没有被覆盖的点pa = find(l)，如果后面第一个没有被覆盖的点已经大于r了，就不需要覆盖了
否则，需要覆盖，即将其祖宗节点置为p[pa] = find(pa + 1)

pa的含义其实就是第一个可以被染色的馒头
"""
import sys

sys.setrecursionlimit(1000000)

input = sys.stdin.readline
print = sys.stdout.write

def find(x):
    if x != p[x]:
        p[x] = find(p[x])
    return p[x]

n, m, P, Q = map(int, input().strip().split())
p = [i for i in range(1000001)]  # 初始化下标
color = [0 for _ in range(1000001)]
# m次染色
for i in range(m, 0, -1):
    l = min((i * P + Q) % n + 1, (i * Q + P) % n + 1)
    r = max((i * P + Q) % n + 1, (i * Q + P) % n + 1)

    pa = find(l) # 找到l后面第一个没有被覆盖的左端点
    # 如果这个左端点已经超过了r，就退出，且不用修改颜色
    while pa <= r:
        color[pa] = i  # 将这个未被覆盖的左端点染色
        p[pa] = find(pa + 1)
        pa = find(pa)

for i in range(1, n + 1):
    print(str(color[i]) + '\n')