参考 Efficient and easy segment trees, By Al.Cash

def build():
    for i in range(n - 1, 0, -1):
        t[i] = max(t[i << 1], t[i << 1 | 1])

def modify(p, value):
    p += n
    t[p] = max(t[p], value)
    while p > 1:
        t[p >> 1] = max(t[p], t[p^1])
        p >>= 1

def query(l, r):
    res = 0
    l += n; r += n
    while l < r:
        if l & 1:
            res = max(res, t[l])
            l += 1
        if r & 1:
            r -= 1
            res = max(res, t[r])
        l >>= 1; r >>= 1
    return res

m, p = map(int, input().split())
n = m
t = [0] * ((n + 10) << 1)

i = last = 0
while m:
    op, x = input().split()
    x = int(x)
    if op == "Q":
        last = query(i - x, i)
        print(last)
    else:
        modify(i, (last + x) % p)
        i += 1
    m -= 1


# m, p = map(int, input().split())
# n = 0
# all_cmds = []
# while m:
#     op, x = input().split()
#     x = int(x)
#     all_cmds.append((op, x))
#     if op == "A": n += 1
#     m -= 1

# t = [0] * ((n + 10) << 1)

# i, last = 0, 0
# for op, x in all_cmds:
#     if op == "Q":
#         last = query( i - x, i)
#         print(last)
#     else:
#         modify(i, (last + x) % p)
#         i += 1

y总普适递归版(python实现会超时)

class Node:
    l, r, v = 0, 0, 0

def pushup(u):
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v)

def build(u, l, r):
    tr[u].l, tr[u].r = l, r
    if l == r: return 
    mid = (l + r) >> 1
    build(u << 1, l, mid)
    build(u << 1 | 1, mid + 1, r)

def query(u, l, r):
    if tr[u].l >= l and tr[u].r <= r: return tr[u].v
    v = 0
    mid = (tr[u].l + tr[u].r) >> 1
    if l <= mid: v = query(u << 1, l, r)
    if r > mid: v = max(v, query(u << 1 | 1, l, r))
    return v

def modify(u, x, v):
    if tr[u].l == tr[u].r == x: tr[u].v = v; return 
    mid = (tr[u].l + tr[u].r) >> 1
    if x <= mid: modify(u << 1, x, v)
    else: modify(u << 1 | 1, x, v)
    pushup(u)

m, p = map(int, input().split())

N = 200010
tr = [Node() for _ in range(N * 4)]
build(1, 1, m)

n = last = 0

while m:
    op, x = input().split()
    x = int(x)
    if op == 'Q':
        last = query(1, n - x + 1, n)
        print(last)
    else:
        modify(1, n + 1, (last + x) % p)
        n += 1
    m -= 1