Bài này có thể sử dụng sweepline Mo, cách giải có thể xem ở https://codeforces.com/blog/entry/83248 (phần 617E với nhiều số khác nhau).
Ta chọn tập S là tập các số có số bit bật bằng k.
Đpt khoảng $$O(n(\frac{A}{\sqrt{\log(A)}}+\sqrt{n})).$$
Code mẫu:
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
struct Query
{
int l, r, id, c;
};
const int NM = 100000;
const int B = 320;
int tempcount[16384];
vector<int> set7[15];
vector<Query> iv[100001];
void init()
{
for (int i = 0; i < 16384; i++)
set7[__builtin_popcountll(i)].push_back(i);
}
void Yoshi()
{
// Complexity: n(A/sqrt(lgA)+sqrtn), n+A mem complexity
int n, q, k;
cin >> n >> q >> k;
vector<int> p(n);
for (auto &i : p)
cin >> i;
vector<Query> qu;
for (int i = 0; i < q; i++)
{
int l, r;
cin >> l >> r;
l--, r--;
qu.push_back({l, r, i, 0});
}
sort(qu.begin(), qu.end(), [](Query &a, Query &b) {
if (a.l / B == b.l / B)
return a.r < b.r;
return a.l / B < b.l / B;
});
int cl = 0, cr = -1;
for (int i = 0; i < q; i++)
{
if (cr < qu[i].r)
{
iv[cl].push_back({cr + 1, qu[i].r, i, -1});
cr = qu[i].r;
}
if (qu[i].l < cl)
{
iv[cr + 1].push_back({qu[i].l, cl - 1, i, 1});
cl = qu[i].l;
}
if (qu[i].r < cr)
{
iv[cl].push_back({qu[i].r + 1, cr, i, 1});
cr = qu[i].r;
}
if (cl < qu[i].l)
{
iv[cr + 1].push_back({cl, qu[i].l - 1, i, -1});
cl = qu[i].l;
}
}
vector<int> ansPrev(n + 1), ansThere(n + 1), ans(q), fans(q);
for (int i = 1; i <= n; i++)
{
ansPrev[i] = ansPrev[i - 1] + tempcount[p[i - 1]];
// add p[i-1]
for (auto &j : set7[k])
tempcount[p[i - 1] ^ j]++;
for (auto [l, r, i, c] : iv[i])
{
int g = 0;
for (int pos = l; pos <= r; pos++)
g += tempcount[p[pos]];
ans[i] += c * g;
}
ansThere[i] = ansThere[i - 1] + tempcount[p[i - 1]];
}
int curans = 0;
for (int i = 0; i < q; i++)
{
curans += ans[i];
fans[qu[i].id] = curans + ansPrev[qu[i].r + 1] + ansThere[qu[i].l];
}
for (int i = 0; i < q; i++)
cout << fans[i] << endl;
}
signed main()
{
#ifndef yoshi_likes_e4
ios::sync_with_stdio(0);
cin.tie(0);
if (fopen(problem ".inp", "r"))
{
freopen(problem ".inp", "r", stdin);
freopen(problem ".out", "w", stdout);
}
#endif
init();
int t = 1;
#if multitest
cin >> t;
#endif
while (t--)
Yoshi();
}
```
pt48583994
Created at
0 likes