Poi 的新加法（Easy Version）

思路

题目定义了一种"二进制只进位加法" ，只做一次进位、不考虑连锁进位。先搞清楚这个运算到底在干嘛。

在标准二进制加法中， 的过程是：先算本位（XOR），再算进位（AND 左移一位），然后把进位加回去，重复直到没有新进位。而这道题的运算只做一轮：算出本位和进位之后就停了，不把进位再加回去继续传播。

但仔细想想，，这其实就等于 ！因为一轮进位恰好就是普通加法。

等等，验证一下样例 2：，？可是答案是 0 啊。

所以这个运算不是"一轮进位加法"，而是只保留进位、丢掉本位。也就是说：

$$

验证样例：

  • ，对了
  • ，，对了
  • 五个 31 连续算：，也对了

关键观察：值会迅速归零

每次操作 ，相当于先 AND 再左移一位。AND 操作只会让 1 的个数不增，左移又把最低位变成 0。

假设数组元素最多有 个二进制位（比如 ），那么经过至多 次操作后，结果的所有有效位都被移出范围，必然变成 0。

所以对于任何查询 ：

  • 如果 ，答案直接就是 0
  • 否则最多只需要迭代 步

每个查询的时间复杂度是 ，其中 大约是 40。总时间 ，完全够用。

实现

直接暴力模拟，遇到 0 就提前退出：

cur = a[l]
for i = l+1 to r:
    cur = 2 * (cur & a[i])
    if cur == 0: break

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        int n, q;
        cin >> n >> q;
        vector<long long> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];

        while(q--){
            int l, r;
            cin >> l >> r;
            l--; r--;
            long long cur = a[l];
            for(int i = l+1; i <= r; i++){
                cur = 2LL * (cur & a[i]);
                if(cur == 0) break;
            }
            cout << cur << "\n";
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine().trim());
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());
            long[] a = new long[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Long.parseLong(st.nextToken());
            }
            while (q-- > 0) {
                st = new StringTokenizer(br.readLine());
                int l = Integer.parseInt(st.nextToken()) - 1;
                int r = Integer.parseInt(st.nextToken()) - 1;
                long cur = a[l];
                for (int i = l + 1; i <= r; i++) {
                    cur = 2L * (cur & a[i]);
                    if (cur == 0) break;
                }
                sb.append(cur).append('\n');
            }
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

t = int(input())
out = []
for _ in range(t):
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    for __ in range(q):
        l, r = map(int, input().split())
        l -= 1; r -= 1
        cur = a[l]
        for i in range(l + 1, r + 1):
            cur = 2 * (cur & a[i])
            if cur == 0:
                break
        out.append(str(cur))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    let t = parseInt(lines[idx++]);
    const res = [];
    while (t-- > 0) {
        const [n, q] = lines[idx++].split(' ').map(Number);
        const a = lines[idx++].split(' ').map(BigInt);
        for (let qi = 0; qi < q; qi++) {
            let [l, r] = lines[idx++].split(' ').map(Number);
            l--; r--;
            let cur = a[l];
            for (let i = l + 1; i <= r; i++) {
                cur = 2n * (cur & a[i]);
                if (cur === 0n) break;
            }
            res.push(cur.toString());
        }
    }
    console.log(res.join('\n'));
});

复杂度分析

  • 时间复杂度：，其中 是二进制位数（约 40）。每次操作左移一位，最多 步后结果必然为 0，因此每个查询最多迭代 次。
  • 空间复杂度：，存储数组。