P8969 分块
Usada_Pekora
·
·
题解
以下用 \mathrm{popc} 代替 \mathrm{popcount}。
先考虑全局加全局 \mathrm{popc} 怎么做。
维护一个 tag 表示目前全局加了多少，于是加法变成了 O(1) 的。
查询取决于你用什么东西去维护这个映射，可以做到 $O(1),O(\log\log V), O(\log V)$ ，这不重要，不作展开。
然后你发现这个东西就可以搬到一些数据结构上维护了，当然线段树上怎么维护我也不会，所以我要写分块。
整块的维护我们按上面的做法维护就好了，关键是散块，对散块的加操作会破坏掉整个映射（可能有 $a_i=a_j$，但是你需要对 $a_j$ 加上一个数），维护映射的 $\mathrm{popc}$ 操作会破坏掉加法的 `tag`。
于是你要对这个散块把该传的标记都传下去，然后维护一个新的映射，这个过程是 $O(B+\log V)$ 的，$B$ 是块长。
然后就可以分析复杂度了。
加法是 $O(q(B+\log V+\frac{n}{B}))$。
对于 $\mathrm{popc}$ 考虑分析势能，变颜色的复杂度是 $O(B+\log V)$（第一次 $\mathrm{popc}$ 或者散块重构），然后最多变 $O(q)$ 次，所以是 $O(q(B+\log V))$，直接 $\mathrm{popc}$ 的复杂度是 $O(q\frac{n}{B}\log V)$。
查询不是瓶颈，反正不高于 $O(q\log V)$。
同时还解决了区间求和。
理论上 $B=\sqrt{n\log V}$ 是最优的，此时复杂度 $O(q\sqrt{n\log V})$，当然性能瓶颈在于重构，所以小一点总是好的。
```cpp
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const int N = 3e5 + 5, S = 389, B = 777, LG = 51;
int n, m, bel[N], st[B], ed[B], siz[B], tmp[LG];
bool pope[B];
ll a[N], tag[B], buk[LG];
pll ys[B][LG];
inline void rebuild(int bid) {
if (!pope[bid]) {
for (int i = st[bid]; i <= ed[bid]; i++)
a[i] += tag[bid];
} else {
for (int i = 1; i <= siz[bid]; i++)
buk[ys[bid][i].fi] = ys[bid][i].se + tag[bid];
for (int i = st[bid]; i <= ed[bid]; i++)
a[i] = buk[a[i]];
}
pope[bid] = false;
tag[bid] = 0;
}
inline void mod_add(int l, int r, ll k) {
int p = bel[l], q = bel[r];
if (p == q) {
rebuild(p);
for (int i = l; i <= r; i++)
a[i] += k;
} else {
rebuild(p);
for (int i = l; i <= ed[p]; i++)
a[i] += k;
for (int i = p + 1; i < q; i++)
tag[i] += k;
rebuild(q);
for (int i = st[q]; i <= r; i++)
a[i] += k;
}
}
inline void mod_pop(int l, int r) {
int p = bel[l], q = bel[r];
if (p == q) {
rebuild(p);
for (int i = l; i <= r; i++)
a[i] = __builtin_popcountll(a[i]);
} else {
rebuild(p);
for (int i = l; i <= ed[p]; i++)
a[i] = __builtin_popcountll(a[i]);
for (int i = p + 1; i < q; i++) {
if (!pope[i]) {
memset(tmp, -1, sizeof tmp), siz[i] = 0;
for (int j = st[i]; j <= ed[i]; j++) {
a[j] = __builtin_popcountll(a[j] + tag[i]);
tmp[a[j]] = a[j];
}
for (int j = 0; j < LG; j++)
if (~tmp[j])
ys[i][++siz[i]] = pll(tmp[j], tmp[j]);
} else {
for (int j = 1; j <= siz[i]; j++)
ys[i][j].se = __builtin_popcountll(ys[i][j].se + tag[i]);
}
pope[i] = true;
tag[i] = 0;
}
rebuild(q);
for (int i = st[q]; i <= r; i++)
a[i] = __builtin_popcountll(a[i]);
}
}
inline ll query(int x) {
int p = bel[x];
if (!pope[p])
return a[x] + tag[p];
return lower_bound(ys[p] + 1, ys[p] + siz[p] + 1, pll(a[x], 0))->se + tag[p];
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
// freopen("test.in", "r", stdin);
// freopen("dsjaikjf.out", "w", stdout);
cin >> n >> m;
// if (n > 2000) {
// return 0;
// }
// ofstream fout("fdsa.out");
for (int i = 1; i <= n; i++)
cin >> a[i];
const int sq = sqrt(n / 2);
for (int i = 1; i <= n; i++)
bel[i] = (i - 1) / sq + 1;
for (int i = 1; i <= bel[n]; i++)
st[i] = ed[i - 1] + 1, ed[i] = st[i] + sq - 1;
ed[bel[n]] = n;
while (m--) {
char op;
int l, r;
ll k;
cin >> op;
if (op == 'A') {
cin >> l >> r >> k;
mod_add(l, r, k);
} else if (op == 'P') {
cin >> l >> r;
mod_pop(l, r);
} else {
cin >> l;
cout << query(l) << '\n';
}
// fout << op << ": ";
// for (int i = 1; i <= n; i++)
// fout << query(i) << ' ';
// fout << endl;
}
return 0;
}
```