Solutions of Bit counting

Select solution language

pt48583994 Created at 1 likes

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(); }$