C++ AC版本

#include <stdio.h>
#include <algorithm>
using namespace std;


struct Node {
    int start;          // 区间开始位置
    int end;            // 区间结束位置
    int max_val;        // 区间最大值
}__global_nodes[200005*4] ;

class SegmentTree {
private:
    Node* __nodes;      // 节点数组
    int __n;            // 区间为0到n-1

    // 更新单个位置的数值
    void __update_single(int node_idx, int pos, int val) {
        Node& node = __nodes[node_idx];

        if (node.start == node.end) {
            node.max_val = val;
            return;
        }

        int mid = (node.start + node.end) >> 1;
        if (pos <= mid) {
            __update_single(node_idx*2+1, pos, val);
        } else {
            __update_single(node_idx*2+2, pos, val);
        }

        node.max_val = max(__nodes[node_idx*2+1].max_val, __nodes[node_idx*2+2].max_val);
    }

    // 获取区间统计信息
    int __get_val(int node_idx, int start, int end) {
        Node& node = __nodes[node_idx];
        if (node.start == start && node.end == end) {
            return node.max_val;
        }

        int mid = (node.start + node.end) >> 1;
        if (end <= mid) {
            return __get_val(node_idx*2+1, start, end);
        } else if (start >= mid+1) {
            return __get_val(node_idx*2+2, start, end);
        } else {
            int val1 = __get_val(node_idx*2+1, start, mid);
            int val2 = __get_val(node_idx*2+2, mid+1, end);
            return max(val1, val2);
        }
    }

public:
    SegmentTree(int n, Node* pnodes) {
        __n = n;
        __nodes = pnodes;
        __nodes[0] = {0, n-1, 0};

        for (int i = 0; i < __n << 2; i++) {
            if (__nodes[i].start == __nodes[i].end and __nodes[i].end == __n-1) {
                break;
            }

            int mid = (__nodes[i].start + __nodes[i].end) / 2;
            __nodes[i*2+1] = {__nodes[i].start, mid, 0};
            __nodes[i*2+2] = {mid+1, __nodes[i].end, 0};
        }
    }

    // 更新单个数据接口
    void update_single(int pos, int val) {
        __update_single(0, pos, val);
    }

    // 获取区间统计数据接口
    int get_val(int start, int end) {
        return __get_val(0, start, end);
    }
};

int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);
    int m, p;
    scanf("%d %d", &m, &p);


    char cmd[5];
    int val;
    SegmentTree tree(m, __global_nodes);

    int num_cnt = 0;
    int last_ans = 0;
    for (int i = 0; i < m; i++) {
        scanf("%s %d", cmd, &val);
        if (cmd[0] == 'A') {
            tree.update_single(num_cnt++, (val+last_ans) % p);
        } else {
            int end = num_cnt-1;
            int start = end - val + 1;
            start = max(start, 0);
            last_ans = tree.get_val(start, end);

            printf("%d\n", last_ans);
        }
    }

    return 0;
}

一模一样的算法用Python超时，C++才过的了，什么鬼

Python超时版本

from typing import List
import sys


class SegmentTreeLazy:
    class Node:
        def __init__(self, start, end):
            self.start = start      # 区段开始位置
            self.end = end          # 区段结束位置
            self.data = 0           # 区段中的信息
            self.left = None        # 左节点
            self.right = None       # 右节点


    # 更新单个数据
    def _update_single(self, root, idx, data):
        if root.start == root.end and root.start == idx:
            root.data += data
            return root.data

        else:
            mid = (root.start + root.end) // 2

            if idx <= mid:
                root.data = max(self._update_single(root.left, idx, data), root.right.data)
            else:
                root.data = max(root.left.data, self._update_single(root.right, idx, data))

            return root.data

    # 获取区间数据
    def _get_data(self, root, start, end):
        if root.start == start and root.end == end:
            # 节点刚好就表示[start, end]区间，不用分裂新节点
            return root.data

        else:
            mid = (root.start + root.end) // 2

            if end <= mid:
                return self._get_data(root.left, start, end)
            elif start >= mid + 1:
                return self._get_data(root.right, start, end)
            else:
                return max(self._get_data(root.left, start, mid), self._get_data(root.right, mid+1, end))


    def update_single(self, idx, data):
        self._update_single(self.root, idx, data)

    def get_data(self, start, end):
        return self._get_data(self.root, start, end)

    def __init__(self, n):
        self.__nodes = [self.Node(0, 0) for _ in range(4*n)]
        nodes = self.__nodes
        nodes[0].start, nodes[0].end = 0, n - 1
        self.root = self.__nodes[0]

        for i in range(4*n):
            if nodes[i].start == n-1 and nodes[i].end == n-1:
                break

            mid = (nodes[i].start + nodes[i].end) // 2
            nodes[i].left = nodes[2*i+1]
            nodes[i].left.start, nodes[i].left.end = nodes[i].start, mid

            nodes[i].right = nodes[2*i+2]
            nodes[i].right.start, nodes[i].right.end = mid+1, nodes[i].end


m, p = map(int, input().split())
tree = SegmentTreeLazy(m)
num_cnt = 0
last_ans = 0

ans = []

for i in range(m):
    s = sys.stdin.readline()
    cmd, val = s.split()
    val = int(val)

    if cmd == 'A':
        tree.update_single(num_cnt, (val + last_ans) % p)
        num_cnt += 1
    else:
        end = num_cnt-1
        start = end - val + 1
        start = max(0, start)
        last_ans = tree.get_data(start, end)
        ans.append(last_ans)

for val in ans:
    sys.stdout.write(str(val) + "\n")