题解 | #Poi 的新加法（Easy Version）#

题目链接

题目描述

Poi 定义了一种新的加法运算 $f(x, y)$ ，它只保留二进制加法中的进位部分。其形式化定义为： $f(x, y) = (x \ \& \ y) \ll 1$ 其中 & 代表按位与运算，<< 1 代表左移一位（相当于乘以2）。

给定一个长度为 $n$ 的序列 $a$ 。现有 $q$ 次查询，每次查询给定一个区间 $[l, r]$ ，要求计算将该运算 $f$ 连续地作用于区间内元素的结果，即： $f(\dots f(f(a_l, a_{l+1}), a_{l+2}), \dots, a_r)$

输入:

第一行一个整数 $T$ ，表示测试用例数。
每个测试用例：
- 第一行两个整数 $n, q$ ，表示序列长度和查询次数。
- 第二行 $n$ 个整数，表示序列 $a$ 的元素。
- 接下来 $q$ 行，每行两个整数 $l, r$ ，表示查询区间。

输出:

对每次查询，输出一个整数作为结果。

解题思路

本题是此问题的“简单版本”，其数据范围相对较小，这提示我们可以使用一种直接的方法来解决。

问题的核心是理解并实现题目定义的运算 $f(x, y)$ ，并将其依次应用在指定区间的元素上。运算 $f(x, y) = (x \ \& \ y) \ll 1$ 不是一个标准的代数运算，我们无法直接判断它是否满足结合律等性质以进行预计算优化（例如使用前缀和或线段树）。

结合律验证： $f(f(x, y), z) = (((x \ \& \ y) \ll 1) \ \& \ z) \ll 1$
$f(x, f(y, z)) = (x \ \& \ ((y \ \& \ z) \ll 1)) \ll 1$ 显然，这两个表达式不相等，所以运算 $f$ 不满足结合律。

因此，我们不能改变运算的顺序，必须严格按照从左到右的顺序进行计算。对于“简单版本”， $n$ 和 $q$ 的规模（均不超过1000）允许我们对每次查询都进行一次暴力的线性扫描。

算法步骤如下：

对于每个查询 [l, r]：
创建一个变量 current_result，并用区间的第一个元素 $a_l$ 初始化它。注意，由于位运算中存在左移操作，结果可能会超出普通整型范围，因此最好使用长整型 (long long in C++, long in Java) 来存储。
从区间的第二个元素 $a_{l+1}$ 开始，遍历到 $a_r$ 。
在循环中，不断更新 current_result：current_result = f(current_result, a_i)，即 current_result = (current_result & a_i) << 1。
循环结束后，current_result 就是本次查询的最终答案。

这种方法的单个查询时间复杂度为 $\mathcal{O}(r-l)$ ，总时间复杂度为 $\mathcal{O}(q \cdot n)$ ，对于本题的数据范围是完全可以接受的。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        // 使用 long long 防止左移操作导致溢出
        long long current_result = a[l - 1];
        for (int j = l; j < r; ++j) {
            // 严格按顺序执行 f 运算
            current_result = (current_result & a[j]) << 1;
        }
        cout << current_result << endl;
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int q = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            // 使用 long 防止左移操作导致溢出
            long currentResult = a[l - 1];
            for (int j = l; j < r; j++) {
                // 严格按顺序执行 f 运算
                currentResult = (currentResult & a[j]) << 1;
            }
            System.out.println(currentResult);
        }
    }
}

def solve():
    # 读取 n 和 q
    n, q = map(int, input().split())
    # 读取数组 a
    a = list(map(int, input().split()))
    
    for _ in range(q):
        # 读取查询区间 l 和 r
        l, r = map(int, input().split())
        # Python 的整数类型自动处理大数，无需担心溢出
        current_result = a[l - 1]
        for i in range(l, r):
            # 严格按顺序执行 f 运算
            current_result = (current_result & a[i]) << 1
        print(current_result)

# 读取测试用例数
t = int(input())
for _ in range(t):
    solve()

算法及复杂度

算法：暴力模拟、迭代计算
时间复杂度：每个查询需要 $\mathcal{O}(r-l)$ 的时间，总共 $q$ 个查询，所以每个测试用例的总时间复杂度为 $\mathcal{O}(\sum (r_i - l_i))$ ，最坏情况下是 $\mathcal{O}(q \cdot n)$ 。
空间复杂度： $\mathcal{O}(n)$ ，主要用于存储输入的序列 $a$ 。