异或询问[2020 CCPC Wannafly WC Day6]

发表于 分类于

题意

给一序列 $a$，定义 $f(x)=\sum_{i=1}^n[a_i\leq x]$，$q$ 组询问，求 $\sum_{i=l}^rf(i\ xor\ x)^2\bmod 998244353$

$n,q\leq 10^5,0\leq a_i,l,r,x < 2^{30}$

题解

先不考虑 $x$ 的限制。

设 $g(n)=\sum_{i=0}^nf(i)^2$，变成求 $g(r)-g(l-1)$。

这个 $g$ 可以二分算出来。时间复杂度 $O(\log n)$

然后考虑 $x$ 的限制。

发现当 $x$ 前几位相同时，$i\ xor\ x$是一段连续的区间。

枚举前 $k$ 位相同即可。

时间复杂度 $O(n\log n\log a_i)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <complex>
#include <utility>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define com complex<db>
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) (x&(-x))
#define fo(i,j,w) for(int i=(j),end_i=(w);i<=end_i;i++)
#define fd(i,j,w) for(int i=(j),end_i=(w);i>=end_i;i--)

const ll mod=998244353;//module
template<typename T>
inline void Add(T &x,T y){x+=y; if(x>=mod) x-=mod;}
template<typename T>
inline void Mul(T &x,T y){(x*=y)%=mod;}
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define N 100010
ll s[N],b[N],a[N];
int n,q,m;
inline ll ask(int x)
{
	int y=upper_bound(b+1,b+m+1,x)-b-1;
	if(!y) return 0;
	ll w=upper_bound(a+1,a+n+1,b[y])-a-1;
	return (s[y-1]+(ll)(x-b[y]+1)*w%mod*w)%mod;
}
inline ll ask(int x,int y) {return (mod+ask(y)-ask(x-1))%mod;}
inline ll calc(int r,int x)
{
	if(r<0) return 0;
	int u=0,t=0,d=0;
	ll ans=0;
	fd(i,30,0)
	{
		u=(x>>i)&1;
		t=d|(u<<i);
		if(r>>i&1) Add(ans,ask(t,t+(1<<i)-1)),d|=((1<<i)^(u<<i));
		else d|=(u<<i);
	}
	Add(ans,ask(d,d));
	return ans;
}
int main()
{
	n=read(); q=read();
	fo(i,1,n) a[i]=b[i]=read();
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	m=unique(b+1,b+n+1)-b-1;
	ll w;
	fo(i,1,m-1)
	{
		w=upper_bound(a+1,a+n+1,b[i])-a-1;
		s[i]=(s[i-1]+(ll)(b[i+1]-b[i])*w%mod*w)%mod;
	}
	//fo(i,1,m-1) printf("%d ",s[i]);
	int l,r,x;
	fo(_,1,q)
	{
		l=read(),r=read(); x=read();
		printf("%d\n",(calc(r,x)-calc(l-1,x)+mod)%mod);
	}
	return 0;
}