算法题：公会动乱 - 禁断之腕·尼古拉

问题描述

我觉得啊……你还是放弃比较好喔
因为我是怪物，一定会把你弄坏的
……如果这样你都不介意的话，也不是不行
只是坏了也没什么好事喔……？

尼古拉拥有独特的思维模式

对于尼古拉而言，a+b 的意思是将 a 和 b 都转化为二进制，然后对于相应的每一位数进行加法但不进位
具体地，对于二进制的每一位而言，0+0=0，0+1=1，1+0=1，1+1=0人们称这种计算模式为“按位异或”
现在尼古拉有一个序列，他多次想知道，对于一个区间内的所有数的和，他的计算结果与正常加法计算的差是多少

输入格式

第一行一个整数 n，m 表示序列长度和询问次数
接下来一行，n 个整数 a_i 表示序列的数
接下来 m 行，每行两个整数 l,r 表示询问的区间

输出格式

共 T 行，每行一个整数表示答案

样例

输入

5 3
1 5 2 1 1
1 5
2 3
3 5

输出

4
0
2

数据范围

数据保证 1≤T≤100，1≤n≤10⁵，1≤m≤10⁵，1≤ai≤10⁴

解决方案

思路

前缀和

代码

#include <iostream>

using namespace std;

const int N = 1e5 + 5;

int main() {

    int n, m;
    cin >> n >> m;

    //前缀和
    static int sum_normal[N];
    static int sum_xor[N];
    for (int i = 1; i <= n; ++i) {
        int t;
        cin >> t;
        sum_normal[i] = sum_normal[i - 1] + t;
        sum_xor[i] = sum_xor[i - 1] ^ t;
    }

    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        cout << (sum_normal[r] - sum_normal[l - 1]) - (sum_xor[r] ^ sum_xor[l - 1]) << endl;
    }

    return 0;
}