题解：AT_arc216_c [ARC216C] Count Power of 2
EricWan
·
·
题解
:::error[我怎么想到用分治的]
我以为想要合法，区间元素极差的大小是 O(\log V) 的，然后就可以分治然后随便算算。
然后吃了两个罚时。
然后继续思考，想到了正解。好像改吧改吧就对了。
:::
一些约定：\
对于非负整数 x，\operatorname{lowbit}(x)=\min\limits_{2^k\operatorname{and}x\neq0} 2^k。\
对于非负整数 x，\operatorname{topbit}(x)=\max\limits_{2^k\operatorname{and}x\neq0} 2^k。\
---
可以分治。
具体的，我们要求 $l\in[L,mid]$ 且 $r\in[mid+1,R]$ 的合法区间数量。
$$\sum_{i=l}^ra_i=\sum_{i=l}^{mid}a_i+\sum_{i=mid+1}^ra_i$$
这是分治的第一步肯定要做的。我们研究一下能凑成 $2^k$ 的两个数有什么性质。因为他们都是正数，所以为了进位进位进位缩成一个 $2^k$，肯定需要 $\operatorname{lowbit}$ 向等，然后画一画就知道需要让两者的 $\operatorname{lowbit}$ 上面，较大的 $\operatorname{topbit}$ 及下面互补，也就是 $a+b=2^k$ 需要让 $\operatorname{lowbit}(a)=\operatorname{lowbit}(b)$，$a\operatorname{xor}b=2^k-2\times\operatorname{lowbit}(a)$。
首先我们肯定要分讨唯一的 $\operatorname{topbit}$ 在哪一侧上，把另一侧的前缀和按 $\operatorname{lowbit}$ 存储入若干个桶中，为了刻画 $a\operatorname{xor}b=2^k-2\times\operatorname{lowbit}(a)$ 的条件，我们使用哈希。提前为每一个 $d$ 都生成一个随机值 $hs_d$，我们扫分治的左右区间的时候肯定要维护一个整数集合代表当前这个前缀和的哪些二进制位是 $1$，维护这些位的 $hs$ 值的 $\operatorname{xor}$ 和，给 $hs$ 当然要做一个 $\operatorname{xor}$ 前缀和方便区间查询即可。我们通过左侧集合的哈希值和目标集合的哈希值可以 $\operatorname{xor}$ 出右侧集合的哈希值，找对应的 $\operatorname{lowbit}$ 对应的桶的对应的位置即可。
注意一大堆 $200000$ 可以凑出 $200000+O(\log N)$ 所以你得多处理一些 $hs$ 否则不够用会 WA 一个点。
代码。
其中最主要的且唯一主要的地方就是 `solve(vi a, vi b)`。
```cpp
#define MAXN 1000005
int n, a[MAXN], ans, ans2;
ull hs[MAXN], hss[MAXN];
umpii mp[MAXN];
int onlylb[MAXN];
void solve(vi a, vi b) {
set<int> num; // 存储那个二进制数
ull sum = 0; // 哈希值
vi lbts; // 方便后续清空这次计算用到的桶使用
for (int i : a) {
int t = i;
while (num.count(t)) {
num.erase(t);
sum ^= hs[t];
t++;
}
num.insert(t);
sum ^= hs[t];
int lb = *num.begin();
lbts.push_back(lb);
if (num.size() == 1) {
onlylb[lb]++;
}
mp[lb][sum ^ hs[lb]]++;
}
sum = 0;
num = {};
int nowans = 0;
for (int i : b) {
int t = i;
while (num.count(t)) {
num.erase(t);
sum ^= hs[t];
t++;
}
num.insert(t);
sum ^= hs[t];
int lb = *num.begin();
if (num.size() == 1) {
ans2 += onlylb[lb];
continue;
}
int tb = *--num.end();
ull tmpsum = sum ^ hs[lb];
nowans += mp[lb][tmpsum ^ hss[tb] ^ hss[lb]];
}
for (int i : lbts) {
umpii tmp;
mp[i].swap(tmp);
onlylb[i] = 0;
}
ans += nowans;
}
void solve(int l, int r) {
if (l == r) {
ans++;
return;
}
int mid = (l + r) >> 1;
vi A(a + l, a + mid + 1);
vi B(a + mid + 1, a + r + 1);
reverse(all(A));
solve(A, B);
swap(A, B);
solve(A, B);
solve(l, mid);
solve(mid + 1, r);
}
xorshift<> my_rand;
signed main() {
for (int i = 1; i <= 300001; i++) {
hs[i] = my_rand();
hss[i] = hss[i - 1] ^ hs[i];
}
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i]++;
}
solve(1, n);
cout << ans + ans2 / 2;
return 0;
}
```