题目描述

给定一个长度为 n 的序列 a1,a2,…,an以及一个整数k。现在要进行m次询问，每次询问给定一个区间[l,r]，请你求出共有多少个数对 (i,j) 满足 l≤i<j≤r 且 ai⊕aj 的结果在二进制表示下恰好有 k 个 1。
注：⊕表示按位异或操作。

题目网址：
https://www.acwing.com/problem/content/description/2537/

样例

略

算法1

莫队算法，分块算法+二次离线+第一次分块+第二次按顺序计算

C++ 代码

//这里填你的代码^^
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=100010;

int n,m,k,len; //n: num of data, m: num of query, k: num of bits, len: size of block
int w[N];
ll ans[N];
struct Query{
    int id, l, r;
    ll res;
}q[N];
struct XRange{
    int id, l, r, t;
};
vector<XRange> xr[N]; //xr[i]: 1-i与l-r的交叉结果，需二次离线
int f[N], g[N]; //f: 1-i与w[i+1]可配对的数量, g[i]与w[i]配对的数量

inline int cntBit(int x){
    int res=0;
    for(; x; x=x&(x-1)) res++;
    return res;
}

bool cmp(const Query &a, const Query &b){
    int i=a.l/len, j=b.l/len;
    if(i!=j) return i<j;
    return a.r<b.r;
}

int main(){
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++) scanf("%d", &w[i]);
    vector<int> nums;
    for(int i=0; i< 1<<14; i++)
        if(cntBit(i)==k) nums.push_back(i);
    for(int i=1; i<=n; i++){
        for(auto y: nums) ++g[w[i]^y];
        f[i]=g[w[i+1]];
    }

    for(int i=0, l, r; i<m; i++)
        scanf("%d%d",&l,&r), q[i]={i, l, r};
    len=sqrt(n);
    sort(q, q+m, cmp);

    for(int i=0, L=1, R=0; i<m; i++){
        int l=q[i].l, r=q[i].r;
        if(R<r) xr[L-1].push_back({i, R+1, r, -1}); //要减去的
        while(R<r) q[i].res+=f[R++];
        if(R>r) xr[L-1].push_back({i, r+1, R, 1}); //要加上的
        while(R>r) q[i].res-=f[--R];
        if(L<l) xr[R].push_back({i, L, l-1, -1});
        while(L<l) q[i].res+=f[L-1]+!k, L++;
        if(L>l) xr[R].push_back({i,l,L-1,1});
        while(L>l) q[i].res-=f[L-2]+!k, L--;
    }

    memset(g,0,sizeof g);
    for(int i=1; i<=n; i++){ //二次离线
        for(auto y: nums) ++g[w[i]^y];
        for(auto &rg: xr[i]){
            int id=rg.id, l=rg.l, r=rg.r, t=rg.t;
            for(int x=l; x<=r; x++)
                q[id].res+=g[w[x]]*t;  //能到达这里的次数是所有区间变化大小之和
        }
    }
    for(int i=0; i<m; i++) q[i].res+=q[i-1].res;  //前面计算的只是变化量，这里累加
    for(int i=0; i<m; i++) ans[q[i].id]=q[i].res;
    for(int i=0; i<m; i++) printf("%lld\n", ans[i]);    
}

//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~