正题

题目链接:https://www.luogu.com.cn/problem/P4887

题目大意

给出一个长度为 $n$ 的序列 $a$ 。 $m$ 次询问 $[l, r]$ 求有多少个 $l\leq i< j\leq r$ 满足 $a_i\ xor\ a_j$ 二进制下恰好有 $k$ 个 $1$ 。

$1\leq n,q\leq 10^5,0\leq a_i,k<2^{14}$

解题思路

记 $f (x, i)$ 表示 $1\sim i$ 中有多少个 $a$ 和 $a_x$ 满足条件，假设我们已经知道了区间 $[l, r]$ 的答案，以 $[l,r]\rightarrow [l,r+1]$ 为例，答案会增加 $f (r + 1, r) ? f (r + 1, l ? 1)$ ， $f (r + 1, r)$ 我们可以直接预处理出每个。

至于 $f (r + 1, l ? 1)$ 我们发现我们的桶和 $f (x, i)$ 中的 $i$ 也就是 $l ? 1$ 有关，在 $r$ 移动的过程中 $l ? 1$ 是不变的，所以我们可以将 $r\rightarrow r+k$ 这个过程离线下来，在指针枚举 $l ? 1$ 时统一处理。

其他指针的移动一样处理即可。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const ll N=1e5+10,L=1<<14,T=316;
struct node{
	ll l,r,id;
}q[N];
ll n,m,k,c[L],v[L],pre[N],a[N],s[N],ans[N];
vector<int> b;
vector<node> u[N];
bool cmp(node x,node y)
{return (x.l/T==y.l/T)?(x.r<y.r):(x.l/T<y.l/T);}
signed main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(ll i=1;i<L;i++)c[i]=c[i-(i&-i)]+1;
	for(ll i=0;i<L;i++)
		if(c[i]==k)b.push_back(i);
	if(k>14){
		for(ll i=1;i<=m;i++)
			puts("0");
		return 0;
	}
	for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(ll i=1;i<=n;i++){
		pre[i]=v[a[i]];
		for(ll j=0;j<b.size();j++)
			v[a[i]^b[j]]++;
	}
	for(ll i=1,l,r;i<=m;i++){
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	ll l=1,r=0;
	for(ll i=1;i<=m;i++){
		if(l<q[i].l)u[r].push_back((node){l,q[i].l-1,-i});
		while(l<q[i].l)s[i]+=pre[l],l++;
		if(l>q[i].l)u[r].push_back((node){q[i].l,l-1,i});
		while(l>q[i].l)l--,s[i]-=pre[l];
		if(r<q[i].r)u[l-1].push_back((node){r+1,q[i].r,-i});
		while(r<q[i].r)r++,s[i]+=pre[r];
		if(r>q[i].r)u[l-1].push_back((node){q[i].r+1,r,i});
		while(r>q[i].r)s[i]-=pre[r],r--;
	}
	memset(v,0,sizeof(v));
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<b.size();j++)
			v[a[i]^b[j]]++;
		for(ll j=0;j<u[i].size();j++){
			for(ll x=u[i][j].l;x<=u[i][j].r;x++){
				ll tmp=v[a[x]];
				if(k==0&&x<=i)tmp--;
				if(u[i][j].id>0)s[u[i][j].id]+=tmp;
				else s[-u[i][j].id]-=tmp;
			}
		}
	}
	for(ll i=1;i<=m;i++)
		s[i]+=s[i-1],ans[q[i].id]=s[i];
	for(ll i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}