题解：P10408 「SMOI-R1」Apple

发表于 分类于 ， ， 本文字数： 432 阅读时长 ≈ 2 分钟
P10408 「SMOI-R1」Apple 的题解

分析

暴力做法:

  1. $O(1)$ 修改, $O(2^n)$ 查询.
  2. $O(2^n)$ 高位前缀和修改, $O(1)$ 查询.

考虑将二者合并. 把一个二进制拆成前半段和后半段. 设 $s_{i,j}$ 表示前半段为 i, 后半段为 j 子集的贡献和.

先预处理出来 $2^{\frac{n}{2}}$ 内的各数的子集与超集. 先枚举每个物品, 将编号拆分成前半段和后半段, 再枚举后半段的超集, 计算该物品贡献.

修改时, 先把编号拆分, 再枚举后半段的超集, 加上新值与原值的差值.

查询时, 先拆编号, 再枚举前半段的子集, 求和得到答案.

这样子我们的总时间复杂度可以到 $O(q \times 2^{\frac{n}{2}})$

参考代码

勉强还是能看的.

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
#include <iostream>
#include <vector>
using namespace std;
const int N = 20, K = 10, K2 = (1 << K);
int a[(1 << N) + 5];
long long s[K2 + 5][K2 + 5];
vector<int> ve1[K2 + 5], ve2[K2 + 5];  // 子集 超集
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int l = n / 2;
    int r = n - l;
    int n2 = 1 << n;
    for (int i = 0; i <= n2 - 1; i++) {
        cin >> a[i];
    }
    for (int i = 0; i <= (1 << r) - 1; i++) {
        for (int j = 0; j <= (1 << r) - 1; j++) {
            if ((i | j) == i) {
                ve1[i].push_back(j);
                ve2[j].push_back(i);
            }
        }
    }
    for (int i = 0; i <= n2 - 1; i++) {
        int high = i >> l;
        int low = i & ((1 << l) - 1);
        for (int x : ve2[low]) {
            if (x < (1 << l)) {
                s[high][x] += a[i];
            }
        }
    }

    while (q--) {
        int op, x, y;
        cin >> op;
        if (op == 1) {
            cin >> x;
            long long ans = 0;
            int high = x >> l;
            int low = x & ((1 << l) - 1);
            for (int i : ve1[high]) {
                if (i <= (1 << r) - 1) ans += s[i][low];
            }
            cout << ans << endl;
        } else {
            cin >> x >> y;
            int high = x >> l;
            int low = x & ((1 << l) - 1);
            for (int i : ve2[low]) {
                if (i <= (1 << l) - 1) s[high][i] += y - a[x];
            }
            a[x] = y;
        }
    }
    return 0;
}