给定一个长 (n) 的序列 (a_1,dots,a_n),定义 (f(x)) 为有多少个 (a_i leq x)
有 (q) 次询问,每次给定 (l,r,x),求 (sum_{i=l}^r f(i xor x)^2)
Solution
定义 (S*x={y xor x|y in S}),((x)_i) 表示 (x) 第 (i) 位的值,则所求为 (sum_{yin[L,R]*x} f^2(y)),差分一下,只需要求 (sum_{yin[0,R]*x} f^2(y))
手玩一下可以想到, ([0,R]*x) 一定能被划分为 (O(log n)) 个连续的区间
考虑第 (w) 位
-
如果 (R<2^w),若 ((x)_w=0) 则变为 ([0,R]*x'),若 ((x)_w=1) 则变为 ([2^w,2^w+R]*x'),其中(x'=x & (2^w-1))
-
如果 (Rgeq 2^w),若 ((x)_w=0) 则变为 ([0,2^w-1] + [2^w,R]*x'),后者递归下去即可;若 ((x)_w=1) 则变为 ([2^w,2^{w+1}-1] + [0,R-2^w]*x'),后者同样递归做下去
如果我们能快速完成这种划分,那么问题转化为求 (g(R)=sum_{xleq R} f^2(x)),考虑到这个函数是个分段线性函数,不妨假设 (a_i) 已经排序,我们只需要预处理出序列 (g(a_1),g(a_2),dots, g(a_n)),那么询问时拿着 (R) 在 (a) 序列上二分一下,就可以很容易算出答案。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100005;
const int mod = 998244353;
struct range{int l,r;};
vector<range> xorrange(int r,int x) {
vector <range> v;
v.push_back({r^x,r^x});
int offset=0;
for(int i=30;i>=0;--i) {
if(r<(1<<i)) {
if(x&(1<<i)) {
offset+=(1<<i);
}
}
else {
if(x&(1<<i)) {
v.push_back({(1<<i)+offset,(1<<(i+1))-1+offset});
r^=(1<<i);
}
else {
v.push_back({offset,(1<<i)-1+offset});
r^=(1<<i);
offset+=(1<<i);
}
}
x&=(1<<i)-1;
}
return v;
}
int n,q,a[N],f[N],g[N];
int calc(int x) {
int p = upper_bound(a+1,a+n+1,x) - a-1;
return (g[p] + (x-a[p])*p*p) % mod;
}
int gen(int p,int x) {
vector<range> v=xorrange(p,x);
int ans=0;
for(int i=0;i<v.size();i++) ans+=(calc(v[i].r)-calc(v[i].l-1)+mod)%mod,ans%=mod;
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) g[i]=(g[i-1]+(i-1)*(i-1)%mod*(a[i]-a[i-1]-1)+i*i)%mod;
for(int i=1;i<=q;i++) {
int l,r,x;
cin>>l>>r>>x;
cout<<(gen(r,x)-gen(l-1,x)+mod)%mod<<endl;
}
}