思想值得借鉴。
1. 题意
题目传送门 UOJ
给定长度为 $n$ 的数组，最大为 $2^{128} - 1$，要求支持以下操作：
- $\forall i \in [l, r],\ a(i):= \dfrac{a(i)}{v}$。
- $\forall i \in [l, r],\ a(i) := a(i)$ & $v$。
- 求 $\sum_{i = l}^r a(i)$，答案对 $2^{128}$ 取模。
$n\leq 3\times10^5, q\leq 2 \times 10 ^ 5$，时限 3s，空间 1GB。
2. 解法
$a(i)$ 用 __uint128_t 存储，可能常数有亿点大。
首先观察 $a(i)$ 在操作中不断减小，所以最多被除 $\log a(i)$ 次，存一下该区间有没有非 0 的数，没有的话直接退出。时间复杂度易得为 $O(q(\log n + \log a(i)))$。
对于第二个操作，我们可以先在这个区间上打一个标记，然后可以用一个 128 的数组存下来每一位出现了多少次，然后 &v 的时候直接将对应的 1 位赋值为 0，更新答案即可。时间复杂度为 $O(q\log n\log a(i))$。（然后你会发现 5000 的点都要跑 1s+）
怎么优化呢？
我们只要考虑压缩 128 的数组。这个数组每一个数都不大于 $len$，用 short 就可以存下来，显然信息密度不够。
我们考虑将 128 数组里的每一个位里存的数二进制拆分，然后将答案存入一个 $\log len$ 的数组。
具体来说，比如有一个 $2^5$ 出现了 5 次，那么我们就在 $cnt[0]$ 和 $cnt[2]$ 插入 $2^5$。这样就可以实现一个 $\log a_i$ 向 $\log len$ 的方向转变。
我们再来看，如果 &v 的时候怎么样呢？之间每一位都 &v 就可以了，因为每一位存的是出现 $2^i$ 次的数的总和，而又不会互相干扰。
求和的时候，直接 $\sum cnt(i) \times 2^i$ 就可以了，时间复杂度同样是 $\log len$。
所以我们就可以得到复杂度为 $O(\log n \log len) = O(\log^2 n)$。
总时间复杂度为 $O(q(\log a(i) + \log^2 n))$，空间复杂度 $O(n \log n)$，卡一卡就可以过了。（但是有些 Hack 数据真的毒瘤，$cnt$ 数组用 vector 实现就 T 了，必须使用数组。
总结：可以将一个 $\log a$ 长但存的数不大的数组通过二进制拆分的手段压缩为 $\log len$。
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
| #define l(x) (x << 1)
#define r(x) (x << 1 | 1)
using u128 = __uint128_t;
const u128 Mand = -1;
void pushup(int x)
{
tr[x].any = tr[l(x)].any | tr[r(x)].any;
u128 now = 0;
for (int i = 0; i < tr[x].sz; ++ i){
u128 le = i < tr[l(x)].sz ? tr[l(x)].cnt[i] : 0,
ri = i < tr[r(x)].sz ? tr[r(x)].cnt[i] : 0;
tr[x].cnt[i] = (le ^ ri) ^ now;
now = (le & ri) | ((le ^ ri) & now);
}
}
void update_and(int x, const u128 &v)
{
tr[x].lt &= v;
for (int i = 0; i < tr[x].sz; ++ i) tr[x].cnt[i] &= v;
tr[x].any = 0;
for (int i = 0; i < tr[x].sz; ++ i) tr[x].any |= (tr[x].cnt[i] > 0);
}
void pushdown(int x)
{
if (tr[x].lt == Mand) return;
update_and(l(x), tr[x].lt), update_and(r(x), tr[x].lt);
tr[x].lt = Mand;
}
void update_div(int x, const u128 &v)
{
if (!tr[x].any) return;
if (tr[x].l == tr[x].r)
{
tr[x].cnt[0] /= v, tr[x].any = (tr[x].cnt[0] > 0);
return;
}
pushdown(x);
update_div(l(x), v), update_div(r(x), v);
pushup(x);
}
void modify_and(int x, int l, int r, const u128 &v)
{
if (tr[x].l >= l && tr[x].r <= r) return update_and(x, v);
pushdown(x);
int mid = (tr[x].l + tr[x].r) >> 1;
if (l <= mid) modify_and(l(x), l, r, v);
if (r > mid) modify_and(r(x), l, r, v);
pushup(x);
}
void modify_div(int x, int l, int r, const u128 &v)
{
if (tr[x].l >= l && tr[x].r <= r) return update_div(x, v);
pushdown(x);
int mid = (tr[x].l + tr[x].r) >> 1;
if (l <= mid) modify_div(l(x), l, r, v);
if (r > mid) modify_div(r(x), l, r, v);
pushup(x);
}
|