有趣的科技。Orz lxl。
首先考虑一个裸的莫队解法，用一个桶存一下，每次暴力找新增的贡献即可。
复杂度是 \(O(n \sqrt n \binom{14}k)\)。
显然过不掉啊……
注意到这个 \(O(\binom{14}k)\) 来自于新增的贡献，于是可以考虑优化这一过程。
考虑从 \([l,r]\) 转移到 \([l,r+k]\)，设 \(c(x,[l,r])\) 表示 \(x\) 对 \([l,r]\) 的贡献，则总贡献为 \[
\sum\limits_{i=r+1}^{r+k} c(i,[l,i)) = \sum\limits_{i=r+1}^{r+k} [c(i,[1,i)) - c(i,[1,l))]
\]
于是贡献就被分成了两种：\(c(i,[1,i))\) 和 \(c(i,[1,r])\)。
前一种一定只会有 \(n\) 个，于是一遍 \(O(n \binom{14}k)\) 处理。
后一种，注意到每次转移时，计算贡献的区间都是同一个，而移动的位置只会有 \(O(n \sqrt n)\) 个，于是可以轻易做到总复杂度 \(O(n \binom{14}k + 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
using namespace std;
const int N = 1e5;
const int C = 16384;
int n,m,k,a[N + 5];
int cnt[C + 5],sum[N + 5];
int block,pos[N + 5];
long long ans[N + 5];
struct s_query
{
int l,r,id;
long long ans;
inline bool operator<(const s_query &o) const
{
return pos[l] ^ pos[o.l] ? l < o.l : ((pos[l] & 1) ? r < o.r : r > o.r);
}
} qry[N + 5];
struct s_contrib
{
int l,r,id,w;
};
vector<int> w;
vector<s_contrib> vec[N + 5];
int main()
{
scanf("%d%d%d",&n,&m,&k),block = sqrt(n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),pos[i] = (i - 1) / block + 1;
for(register int i = 1;i <= m;++i)
scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id = i;
if(k > 14)
{
for(register int i = 1;i <= m;++i)
puts("0");
return 0;
}
sort(qry + 1,qry + m + 1);
for(register int i = 0;i < C;++i)
__builtin_popcount(i) == k && (w.push_back(i),1);
for(register int i = 1;i <= n;++i)
{
sum[i] = cnt[a[i]];
for(vector<int>::iterator it = w.begin();it != w.end();++it)
++cnt[a[i] ^ *it];
}
for(register int i = 1,l = 1,r = 0;i <= m;++i)
{
l < qry[i].l && (vec[r].push_back((s_contrib){l,qry[i].l - 1,i,-1}),1);
for(;l < qry[i].l;qry[i].ans += sum[l],++l);
l > qry[i].l && (vec[r].push_back((s_contrib){qry[i].l,l - 1,i,1}),1);
for(;l > qry[i].l;qry[i].ans -= sum[l - 1],--l);
r < qry[i].r && (vec[l - 1].push_back((s_contrib){r + 1,qry[i].r,i,-1}),1);
for(;r < qry[i].r;qry[i].ans += sum[r + 1],++r);
r > qry[i].r && (vec[l - 1].push_back((s_contrib){qry[i].r + 1,r,i,1}),1);
for(;r > qry[i].r;qry[i].ans -= sum[r],--r);
}
memset(cnt,0,sizeof cnt);
for(register int i = 1;i <= n;++i)
{
for(vector<int>::iterator it = w.begin();it != w.end();++it)
++cnt[a[i] ^ *it];
for(vector<s_contrib>::iterator it = vec[i].begin();it != vec[i].end();++it)
for(register int j = it->l;j <= it->r;++j)
qry[it->id].ans += it->w * (cnt[a[j]] - (j <= i && !k));
}
for(register int i = 1;i <= m;++i)
ans[qry[i].id] = (qry[i].ans += qry[i - 1].ans);
for(register int i = 1;i <= m;++i)
printf("%lld\n",ans[i]);
}