LuoguP6562 [SBCOI2020] 归家之路

Description

给定长度为 2n2^n (1n16)\left(1\leq n\leq16\right) 的序列 aa (0ai2321)\left(0\leq a_i\leq2^{32}-1\right) ,下标从 00 开始。
给定 qq (1q2×105)\left(1\leq q\leq2\times10^5\right) 次操作,操作分两种:

  • (1,l,r,k)\left(1,l,r,k\right) (0l,r2n1, 0k2321)\left(0\leq l,r\leq2^n-1,\ 0\leq k\leq2^{32}-1\right) .
    表示对所有 i[0,2n), l&i=l, i&r=ii\in\left[0,2^n\right),\ l\&i=l,\ i\&r=i ,令 ai=ai+ka_i=a_i+k .

  • (2,l,r)\left(2,l,r\right) (0l,r2n1)\left(0\leq l,r\leq2^n-1\right) ,表示求

    ansl,r=(l&i=l, i&r=iai)mod232ans_{l,r}=\left(\sum_{l\&i=l,\ i\&r=i}a_i\right)\bmod2^{32}


Solution

首先,取模可用 unsigned int 自然溢出 解决。
注意到 x&y=x    xyx\&y=x\implies x\subseteq y ,考虑询问如何求 ansl,rans_{l,r} .
显然要考虑 高维前缀和 ,记 sumi=jiajsum_i=\sum\limits_{j\subseteq i}a_j .
x=lowbit(l)=l&lx=lowbit\left(l\right)=l\&-l ,则

ansl,r={0l&rlsumrl&r=l, l=0anslx,ranslx,rxl&r=l, l>0ans_{l,r}=\begin{cases} 0&l\&r\neq l\\ sum_r&l\&r=l,\ l=0\\ ans_{l-x,r}-ans_{l-x,r-x}&l\&r=l,\ l>0 \end{cases}

popcnt(x)popcnt\left(x\right) 为二进制下 xx11 的数量,即 xx 对应的二进制集合的大小。
考虑当 l&r=ll\&r=l 时求 ansl,rans_{l,r} 的单次时间复杂度。
l=0l=0 时即求 sumrsum_r ,可预处理。
l>0l>0 时,令 s=popcnt(l), d=popcnt(rl)s=popcnt(l),\ d=popcnt\left(r-l\right) .
则按递推式可在 O(2s)\mathcal O\left(2^s\right) 的时间内求解 ,直接枚举可在 O(2d)\mathcal O\left(2^d\right) 的时间内求解。
可根据实际情况选择,故单次时间复杂度为 O(2min(s,d))\mathcal O\left(2^{\min\left(s,d\right)}\right) ,即 O(2n)\mathcal O\left(\sqrt{2^n}\right) .

考虑修改操作 (1,l,r,k)\left(1,l,r,k\right) ,可仿照求 ansl,rans_{l,r} 的方法进行。
l&rll\&r\neq l 时,显然无需修改。
l&r=ll\&r=ll>0l>0 时,根据实际情况选择直接修改或递归往下修改。
l&r=ll\&r=ll=0l=0 时,打一个 标记 即可。
显然,修改的单次时间复杂度仍为 O(2n)\mathcal O\left(\sqrt{2^n}\right) .

考虑如何下放标记并维护 sumsum .
下放标记相当于求 逆的 高维前缀和,维护 sumsum 即求 aa 的高维前缀和。
称这样一次操作为 updateupdate 操作,单次时间复杂度为 O(n2n)\mathcal O\left(n2^n\right) .
显然需要控制 updateupdate 的次数,考虑 对操作分块 ,假设分成 mm 块。
询问和修改正常进行,这部分的总时间复杂度为 O(q2n)\mathcal O\left(q\sqrt{2^n}\right) .
每一块 只在最后 updateupdate 一次 ,则更新的总时间复杂度为 O(mn2n)\mathcal O\left(mn2^n\right) .
每一块内 前面有修改 的询问由于标记未下放不能直接求。
每一块更新后用 bb 暂存 aa ,询问中用 bb 代替 aa .
此时,询问直接求得的结果相当于 不考虑块内前面的修改时 的结果。
故这之后只需枚举未考虑的修改将修改的 贡献 加到结果上即可。
当然,也可以将修改全部留到更新时一次性完成。
显然最坏情况下即每一块的前一半是修改,后一半是询问。
因此,这部分的总时间复杂度为 O(q2n2m)\mathcal O\left(\frac{q2^{n-2}}m\right) .

显然取 m=12qnm=\frac12\sqrt\frac q n 时最优,时间复杂度:O(q2n+2nqn)\mathcal O\left(q\sqrt{2^n}+2^n\sqrt{qn}\right) .


Code

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
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;

const int N = (1 << 16) + 5;
const int M = 2e5 + 5;
int n, q, ope, l, r;
ui k, a[N];
int t, m, s, id, cnt[N], lf[M], rg[M];
ui b[N], ki[M], sum[N], tag[N];

void init(void);
void solve(void);
void update(void);
void modify(int l, int r, ui k);
ui query(int l, int r);
ui get_mdf(int x, int l, int r);
int lowbit(int x);

int main(void) {
init();
for (q = 0; q < t; q++) solve();
return 0;
}

void init(void) {
scanf("%d%d", &n, &q), t = q, m = 1 << n, s = 2 * sqrt(q * n);
for (int i = 0; i < m; i++)
scanf("%u", a + i), cnt[i] = cnt[i >> 1] + (i & 1);
}

void solve(void) {
if (!(q % s)) id = 0, update();
scanf("%d%d%d", &ope, &l, &r);
if ((l & r) ^ l) return void(ope == 1 ? scanf("%u", &k) : puts("0"));
if (ope == 1) {
scanf("%u", &k), lf[++id] = l, rg[id] = r, ki[id] = k;
return modify(l, r, k);
}
ui ans = query(l, r);
for (int i = 1; i <= id; i++) ans += get_mdf(i, l, r);
printf("%u\n", ans);
}

void update(void) {
for (int i = 1; i < m; i <<= 1)
for (int j = m - 1; ~j; j--) tag[j ^ i] += (j & i) ? tag[j] : 0;
for (int i = 0; i < m; i++) sum[i] = b[i] = a[i] += tag[i];
memset(tag, 0, m * sizeof(ui));
for (int i = 1; i < m; i <<= 1)
for (int j = 0; j < m; j++) sum[j] += (j & i) ? sum[j ^ i] : 0;
}

void modify(int l, int r, ui k) {
if (cnt[l ^ r] <= n / 2) {
int x = l ^ r;
for (int i = x; i; i = (i - 1) & x) a[l | i] += k;
return a[l] += k, void();
}
if (!l) return tag[r] += k, void();
int x = lowbit(l);
modify(l ^ x, r, k), modify(l ^ x, r ^ x, -k);
}

ui query(int l, int r) {
if (cnt[l ^ r] <= n / 2) {
int x = l ^ r;
ui ans = b[l];
for (int i = x; i; i = (i - 1) & x) ans += b[l | i];
return ans;
}
if (!l) return sum[r];
int x = lowbit(l);
return query(l ^ x, r) - query(l ^ x, r ^ x);
}

inline ui get_mdf(int x, int l, int r) {
l |= lf[x], r &= rg[x];
return (l & r) == l ? (1 << cnt[l ^ r]) * ki[x] : 0;
}

inline int lowbit(int x) { return x & -x; }

Tsukkomi

去年我京出事时我加了个 Luogu 团队:京都动画同好会
在群里认识了 4b @犇犇犇犇SBCOI2020 的出题人之一。
然后就知道了这题,并发现我看不懂官方题解。
前面的都不难,重点是官方题解没说对什么东西分块!
研究了半天依然摸不着头脑后,果断问 4b 去了 ~
可能是我分块题做少了,第一次见对操作分块的题 qwq

Welcome to my other publishing channels