#4706. 异或

题目描述

题解

考虑答案转化为两个前缀和相减，也就是求 $\sum_{i=0}^{n}f^2(i \wedge x)$∑i=0n​f2(i∧x)

考虑最高位，如果 $n$n 在第 $k$k 位是 $0$0 的话，那就变成 $[0,n] \wedge x'$[0,n]∧x′ 或 $[2^k,n+2^k] \wedge x'$[2k,n+2k]∧x′ ， $x'$x′ 是去掉第 $k$k 位的值

如果 $n$n 在第 $k$k 位是 $1$1 的话，那有 $[0,2^k)$[0,2k) 和 $[2^k,n]$[2k,n] 两个范围，其中前面区间和 $x'$x′ 异或肯定还是这个区间内的取值，另一边递归往下做就好了

所以我们现在有 $[0,n]$[0,n] ，如何求 $\sum_{i=0}^nf^2(i)$∑i=0n​f2(i)

考虑把 $a_i$ai​ 排序，然后在每个 $a_i$ai​ 预处理出一个答案，然后我们只要二分到最后一个小于等于 $n$n 的 $a_i$ai​ 即可

效率： $O(30qlogn)$O(30qlogn)

代码

#include <bits/stdc++.h>
#define _(d) while(d(isdigit(c=getchar())))
using namespace std;
int R(){char c;_(!);int x=(c^48);_()x=(x<<3)+(x<<1)+(c^48);return x;}
int ww[20];
void W(int x){
	if (!x){putchar(48);return;}
	int v=0;while(x) ww[++v]=x%10,x/=10;
	for (int i=v;i;i--) putchar(ww[i]^48);
}
const int N=1e5+5,P=998244353;
int n,q,a[N],b[N],B,s[N];
int X(int x){return x>=P?x-P:x;}
int qry(int x){
	int v=upper_bound(b+1,b+B+1,x)-b-1;
	if (!v) return 0;
	int u=upper_bound(a+1,a+n+1,x)-a-1;
	return X(s[v-1]+1ll*u*u%P*(x-b[v]+1)%P);
}
int qry(int m,int x){
	if (m<0) return 0;int v=0,w=0;
	for (int u,y,i=29;~i;i--){
		y=(1<<i);u=(x&y);
		if ((m>>i)&1){
			v=X(v+X(qry((w|u)+y-1)-qry((w|u)-1)+P));
			w|=(y^u);
		}
		else w|=u;
	}
	return X(v+X(qry(w)-qry(w-1)+P));
}
int main(){
	n=R();q=R();
	for (int i=1;i<=n;i++)
		b[++B]=a[i]=R();
	sort(a+1,a+n+1);sort(b+1,b+n+1);
	B=unique(b+1,b+B+1)-b-1;
	for (int v,i=1;i<B;i++){
		v=upper_bound(a+1,a+n+1,b[i])-a-1;
		s[i]=X(s[i-1]+1ll*(b[i+1]-b[i])*v%P*v%P);
	}
	for (int l,r,x;q--;)
		l=R(),r=R(),x=R(),
		W(X(qry(r,x)-qry(l-1,x)+P)),putchar('\n');
	return 0;
}