本文共 2668 字，大约阅读时间需要 8 分钟。

为了解决这个问题，我们需要高效地处理工兵营地的人数变动和查询。线段树是一种适合这种操作的数据结构，因为它可以在O(log n)的时间内完成更新和查询操作。

方法思路

解决代码

import sys
def main():
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for case in range(1, T + 1):
        N = int(input[ptr])
        ptr += 1
        a = list(map(int, input[ptr:ptr + N]))
        ptr += N
        size = 1
        while size < N:
            size <<= 1
        tree = [0] * (2 * size)
        def build(node, start, end):
            if start == end:
                tree[node] = a[start - 1]
            else:
                mid = (start + end) // 2
                build(2 * node, start, mid)
                build(2 * node + 1, mid + 1, end)
                tree[node] = tree[2 * node] + tree[2 * node + 1]
        build(1, 1, size)
        def update(node, start, end, idx, value):
            if start == end:
                tree[node] += value
            else:
                mid = (start + end) // 2
                if idx <= mid:
                    update(2 * node, start, mid, idx, value)
                else:
                    update(2 * node + 1, mid + 1, end, idx, value)
                tree[node] = tree[2 * node] + tree[2 * node + 1]
        def query(node, start, end, l, r):
            if r < start or end < l:
                return 0
            if l <= start and end <= r:
                return tree[node]
            mid = (start + end) // 2
            left = query(2 * node, start, mid, l, r)
            right = query(2 * node + 1, mid + 1, end, l, r)
            return left + right
        while True:
            cmd = input[ptr]
            ptr += 1
            if cmd == 'End':
                break
            if cmd == 'Add':
                i = int(input[ptr])
                j = int(input[ptr + 1])
                ptr += 2
                update(1, 1, size, i, j)
            elif cmd == 'Sub':
                i = int(input[ptr])
                j = int(input[ptr + 1])
                ptr += 2
                update(1, 1, size, i, -j)
            elif cmd == 'Query':
                i = int(input[ptr])
                j = int(input[ptr + 1])
                ptr += 2
                res = query(1, 1, size, i, j)
                print(res)
        print(f"Case {case}:")
if __name__ == "__main__":
    main()

代码解释

通过这种方法，我们可以高效地处理工兵营地的人数变动和查询，确保程序在处理大量数据时也能保持高效。