题解 | #小苯的数组查询（二）#

题目链接

小苯的数组查询（二）

题目描述

给定一个长度为 $n$ 的数组，需要处理 $q$ 次操作。操作分为两种：

1 type x：修改操作。如果 $type=1$ ，则将数组中所有奇数都加上 $x$ ；如果 $type=2$ ，则将数组中所有偶数都加上 $x$ 。
2：查询操作。查询并输出当前数组所有元素的总和。

思路分析

直接模拟每次更新操作，即遍历整个数组对符合奇偶性条件的元素进行修改，时间复杂度为 $O(n)$ 。对于 $q$ 次操作，总时间复杂度为 $O(n \cdot q)$ ，这在 $n$ 和 $q$ 较大时会超时。

我们可以换一个角度，不去维护数组中的每一个具体值，而是维护整个数组的宏观统计信息。具体来说，我们只需要维护三个量：

$sum_{total}$ ：数组中所有元素的总和。
$count_{odd}$ ：数组中奇数的个数。
$count_{even}$ ：数组中偶数的个数。

初始化

在处理操作前，我们首先遍历一次原始数组，用 $O(n)$ 的时间计算出这三个量的初始值。

处理操作

查询操作 (2): 直接输出我们维护的 $sum_{total}$ 即可，时间复杂度为 $O(1)$ 。
修改操作 (1 type x):
1. 更新总和:
  - 如果 $type=1$ （给奇数加 $x$ ），那么总和增加的值等于奇数的个数乘以 $x$ ，即 $sum_{total} \leftarrow sum_{total} + count_{odd} \cdot x$ 。
  - 如果 $type=2$ （给偶数加 $x$ ），那么总和增加的值等于偶数的个数乘以 $x$ ，即 $sum_{total} \leftarrow sum_{total} + count_{even} \cdot x$ 。
2. 更新奇偶数个数:
  - 一个数加上 $x$ 后，其奇偶性是否改变，完全取决于 $x$ 的奇偶性。
  - 如果 $x$ 是偶数，那么 奇数+偶数=奇数，偶数+偶数=偶数。数字的奇偶性不变， $count_{odd}$ 和 $count_{even}$ 均不改变。
  - 如果 $x$ 是奇数，那么 奇数+奇数=偶数，偶数+奇数=奇数。数字的奇偶性会发生反转。
    - 对于 $type=1$ 的操作，所有奇数都变成了偶数。因此，我们将 $count_{odd}$ 的值加到 $count_{even}$ 上，然后将 $count_{odd}$ 置为 $0$ 。
    - 对于 $type=2$ 的操作，所有偶数都变成了奇数。因此，我们将 $count_{even}$ 的值加到 $count_{odd}$ 上，然后将 $count_{even}$ 置为 $0$ 。

通过这种方式，每次修改操作都可以在 $O(1)$ 的时间内完成。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

void solve() {
    int n;
    long long q;
    cin >> n >> q;

    long long count_odd = 0;
    long long count_even = 0;
    long long sum_total = 0;

    for (int i = 0; i < n; ++i) {
        long long val;
        cin >> val;
        if (val % 2 == 0) {
            count_even++;
        } else {
            count_odd++;
        }
        sum_total += val;
    }

    for (int i = 0; i < q; ++i) {
        int type;
        cin >> type;
        if (type == 1) {
            int op_type;
            long long x;
            cin >> op_type >> x;
            if (op_type == 1) { // 给奇数加x
                sum_total += count_odd * x;
                if (x % 2 != 0) { // x是奇数，奇偶性反转
                    count_even += count_odd;
                    count_odd = 0;
                }
            } else { // 给偶数加x
                sum_total += count_even * x;
                if (x % 2 != 0) { // x是奇数，奇偶性反转
                    count_odd += count_even;
                    count_even = 0;
                }
            }
        } else {
            cout << sum_total << endl;
        }
    }
}

int main() {
    // 为处理多组测试用例（虽然本题只有一组，但这是个好习惯）
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    solve();
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int q = sc.nextInt();

        long countOdd = 0;
        long countEven = 0;
        long sumTotal = 0;

        for (int i = 0; i < n; i++) {
            long val = sc.nextLong();
            if (val % 2 == 0) {
                countEven++;
            } else {
                countOdd++;
            }
            sumTotal += val;
        }

        for (int i = 0; i < q; i++) {
            int type = sc.nextInt();
            if (type == 1) {
                int opType = sc.nextInt();
                long x = sc.nextLong();
                if (opType == 1) { // 给奇数加x
                    sumTotal += countOdd * x;
                    if (x % 2 != 0) { // x是奇数，奇偶性反转
                        countEven += countOdd;
                        countOdd = 0;
                    }
                } else { // 给偶数加x
                    sumTotal += countEven * x;
                    if (x % 2 != 0) { // x是奇数，奇偶性反转
                        countOdd += countEven;
                        countEven = 0;
                    }
                }
            } else {
                System.out.println(sumTotal);
            }
        }
    }
}

import sys

def solve():
    n, q = map(int, sys.stdin.readline().split())
    arr = list(map(int, sys.stdin.readline().split()))

    count_odd = 0
    count_even = 0
    sum_total = 0

    for val in arr:
        if val % 2 == 0:
            count_even += 1
        else:
            count_odd += 1
        sum_total += val

    for _ in range(q):
        line = list(map(int, sys.stdin.readline().split()))
        op_type = line[0]

        if op_type == 1:
            type_val, x = line[1], line[2]
            if type_val == 1:  # 给奇数加x
                sum_total += count_odd * x
                if x % 2 != 0:
                    count_even += count_odd
                    count_odd = 0
            else:  # 给偶数加x
                sum_total += count_even * x
                if x % 2 != 0:
                    count_odd += count_even
                    count_even = 0
        else:
            print(sum_total)

solve()

算法及复杂度

算法：宏观状态维护/计数
时间复杂度： $O(n + q)$ 。其中 $O(n)$ 用于初始化统计变量，之后每次操作的复杂度为 $O(1)$ ，总共 $q$ 次操作。
空间复杂度： $O(1)$ （Python代码中为 $O(n)$ 用于存储初始数组，但可以优化为 $O(1)$ ）。我们只需要常数个变量来维护数组的统计信息，而无需存储整个数组。