题解 | Poi 的新加法（Hard Version）

首先得知道两个关于位运算的小结论：

a + b = (a & b) + (a | b)

a | b = (a & b) + (a ^ b)

你自己想一下就知道证明过程了

所以 a + b - (a ^ b) = 2 * (a & b) = （a & b) << 1

那么对于每一个区间查询[l, r]的值，手动模拟一下a[l], a[l + 1], a[l + 2]

那么a[l] + a[l + 1] - (a[l] ^ a[l + 1]) = (a[l] & a[l + 1]) << 1

然后(((a[l] & a[l + 1]) << 1) & a[l + 2]) << 1

注意到的是都会有一个 << 1的操作，那么当二进制整体左移一位，低位补上0，那么(a[l] & a[l + 1]) << 1的二进制最后一位一定为0，再与a[l + 2]进行&操作，最后一位也一定为0。然后有开始<< 1操作，所以虽然说[l, r]区间长度最大为n，但实际上不会超过64次，即：无论区间 [l, r]多长，单次查询的内层循环最多执行 64 次；

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

void solve(){
    int n, q; cin >> n >> q;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i];
    while(q --){
        int l, r; cin >> l >> r;
        int now = a[l];
        for(int i = l + 1; i <= r; i ++){
            now = (now & a[i]) << 1;
            if(!now) break;
        }
        cout << now << endl;
    }
    return ;
}
signed main(){
    HelloWorld;
    
    int tt; cin >> tt;
    while(tt --) solve();
    return 0;
}