P4758 纸牌PK（基础）

解题思路

小童和小程各抽 m 轮纸牌，每轮抽连续的一段（L 到 R 张），谁 m 轮抽到的数字总和更大，谁就赢。我们要想办法又快又准地算出两个人各自的总分。

第一步，先想想直接一个一个加为什么太慢。 如果每轮都从 L 到 R 一张张加，一轮最多有 500000 张牌，m 轮最多 100 轮，最坏情况要加 5 千万次，太慢了，很可能会超时。

第二步，认识神器"前缀和"。 聪明的方法叫"前缀和"（prefix sum）。我们开一个数组 prefixSum，prefixSum[i] 表示前 i 张牌的数字之和，也就是第 1 张加到第 i 张。这个数组可以在读牌的时候顺便建好： prefixSum[i] = prefixSum[i-1] + 第 i 张牌

可以把它想象成一把"刻度尺"：每一格都记下从头量到这里的总长度。

第三步，用前缀和快速求任意一段区间和。 有了 prefixSum，想求任意一段 [L, R] 的和，只需要一步减法： 区间 [L, R] 的和 = prefixSum[R] - prefixSum[L-1]

为什么？prefixSum[R] 是第 1 到 R 张的和，prefixSum[L-1] 是第 1 到 L-1 张的和，两者一减，中间的 L 到 R 张正好被单独算出来。就像用刻度尺先量出到 R 的总长，再减去到 L-1 的长，中间那段就是答案。

第四步，把两个人的分数分别加起来再比较。 先读小童的 m 轮范围，每轮的区间和都加到 totalTong 上；再读小程的 m 轮范围，加到 totalCheng 上。最后比较：

• totalTong 大，输出 T；
• totalCheng 大，输出 C；
• 两个一样大，输出 D。

第五步，注意数据范围，小心溢出。 所有牌最多 500000 张，每张最大 100，一轮区间和最大 5 千万，m 轮加起来可能超过 20 亿，已经超出 int 的范围，所以 totalTong、totalCheng 和 prefixSum 数组都要用 long long。

参考代码

// 纸牌PK：前缀和快速求区间和，比较小童和小程各自m轮的总分大小
#include <cstdio>
using namespace std;

int cardValue[500005];          // 每张纸牌上的数字
long long prefixSum[500005];    // 前缀和数组，prefixSum[i]=前i张牌数字之和

int main() {
    int cardCount, roundCount;
    scanf("%d%d", &cardCount, &roundCount);
    for (int index = 1; index <= cardCount; index++) {
        scanf("%d", &cardValue[index]);
        prefixSum[index] = prefixSum[index - 1] + cardValue[index];   // 一边读一边建前缀和
    }
    long long totalTong = 0, totalCheng = 0;   // 小童、小程各自的总和
    int left, right;
    for (int roundIndex = 0; roundIndex < roundCount; roundIndex++) {   // 先读小童的roundCount轮抽牌范围
        scanf("%d%d", &left, &right);
        totalTong += prefixSum[right] - prefixSum[left - 1];   // 区间[left,right]的和 = prefixSum[right]-prefixSum[left-1]
    }
    for (int roundIndex = 0; roundIndex < roundCount; roundIndex++) {   // 再读小程的roundCount轮抽牌范围
        scanf("%d%d", &left, &right);
        totalCheng += prefixSum[right] - prefixSum[left - 1];
    }
    if (totalTong > totalCheng) printf("T\n");
    else if (totalCheng > totalTong) printf("C\n");
    else printf("D\n");
    return 0;
}

复杂度分析

建前缀和需要 O(n) 的时间，之后每轮区间和只要 O(1) 一次减法，总共 m 轮、两个人共 2m 次查询，所以总时间复杂度是 O(n + m)。n 最大 500000，m 最大 100，几毫秒就能跑完。空间上需要 prefixSum 数组，长度 n+1，空间 O(n)。因为用了 scanf 快速读入，500000 个数也能轻松读进来。