Steven_MengのBlog

传送门

此题思路还是非常巧妙的。

考虑我们莫队的 Add 函数,本质上是往原本的区间里面加上一个数,然后算这个数的贡献。

比如说我们设 $f(x,[l,r])$ 为 $\sum _{i=l}^r [cnt(x \oplus a[i])=k]$(中括号里面为真时,值为 1,$cnt$ 代表计算二进制里面 1 的个数)

那么我们右边界扩展到 $r$ 时,答案加上 $f(a[r],[l,r-1])$。

当我们能 $O(1)$ 或者 $O(\log n)$ 地算出 $f$ 时,时间复杂度正确的,但是显然在这道题里面我们不能。

考虑将 $f(x,[l,r])$ 拆成两个区间 $f(x,[1,l-1]),f(x,[1,r])$(注意图中下标可能有点不同)

注意到 $x$ 永远为 $a[r+1]$,所以 $f(x,[1,r])$ 能够预处理出来。

考虑计算 $f(x,[1,l-1])$。

如果把莫队的移动过程画出来,$f(x,[1,l-1])$ 大概长成什么样子?

长成这个鬼样子。

考虑我们莫队的时间复杂度是如何保证?所有移动次数不超过 $O(n \sqrt n)$,所以我们按照左边绿色区间的长度排序,然后跑一个大暴力,统计所有绿色圆圈的值即可。

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
#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 16384
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int pos[MAXN],a[MAXN],cnt[MAXN],buc[MAXN],Size;
int top,stk[MAXN],sum[MAXN],Ans[MAXN];
struct Query{
int l,r,f,id,ans;
}Q[MAXN];
inline bool operator < (const Query &a,const Query &b){
return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));//奇偶性排序的压行写法
}
int n,m,k;
inline void Init(){
cnt[0]=0;
for (register int i=1;i<MAXM;++i){
cnt[i]=cnt[i>>1]+(i&1);
if (cnt[i]==k) stk[++top]=i;
}
if (cnt[0]==k) stk[++top]=0;
Size=sqrt(n);
for (register int i=1;i<=n;++i){
pos[i]=(i-1)/Size+1;
}
}
vector<Query> S[MAXN];
inline void AddQuery(int pos,int l,int r,int f,int id){
if (pos!=0&&l<=r) S[pos].push_back(Query{l,r,f,id,0});
}
#undef int
int main(){
#define int long long
n=read(),m=read(),k=read();
Init();
if (k>14){
for (register int i=1;i<=m;++i){
puts("0");
}
return 0;
}
for (register int i=1;i<=n;++i){
a[i]=read();
}
for (register int i=1;i<=m;++i){
int l=read(),r=read();
Q[i]=Query{l,r,0,i,0};
}
sort(Q+1,Q+1+m);
//a[i] xor a[j]==x -> a[j]=a[i] xor x
for (register int i=1;i<=n;++i){
for (register int j=1;j<=top;++j) buc[a[i]^stk[j]]++;
sum[i]=buc[a[i+1]];
}
int l=1,r=0;
for (register int i=1;i<=m;++i){
AddQuery(r,l,Q[i].l-1,-1,i);
while (l<Q[i].l) Q[i].ans+=sum[l++-1];

AddQuery(r,Q[i].l,l-1,1,i);
while (l>Q[i].l) Q[i].ans-=sum[--l-1];

AddQuery(l-1,r+1,Q[i].r,-1,i);
while (r<Q[i].r) Q[i].ans+=sum[++r-1];

AddQuery(l-1,Q[i].r+1,r,1,i);
while (r>Q[i].r) Q[i].ans-=sum[r---1];
}
memset(buc,0,sizeof(buc));
for (register int i=1;i<=n;++i){
for (register int j=1;j<=top;++j) buc[a[i]^stk[j]]++;
for (register int p=0;p<S[i].size();++p){
int l=S[i][p].l, r=S[i][p].r, f=S[i][p].f, id=S[i][p].id;
for (register int j=l;j<=r;++j){
int temp=buc[a[j]];
if (k==0&&j<=i) temp--;
Q[id].ans+=f*temp;
}
}
}
for (register int i=1;i<=m;++i) Q[i].ans+=Q[i-1].ans,Ans[Q[i].id]=Q[i].ans;
for (register int i=1;i<=m;++i) printf("%lld\n",Ans[i]);
}

 评论