CF1930F 题解
murder_drones
·
·
题解
简要题意
维护一个值域为 [0,n) 的集合 a，有 q 次插入，在每次插入之后输出以下式子。
\max_x (\max_{i=1}^{\lvert a \rvert} {(a_i \operatorname{or} x)} - \min_{i=1}^{\lvert a \rvert} {(a_i \operatorname{or} x)})
其中 n \le 2^{22}，q \le 10^6，要求强制在线。
题目分析
假设产生答案的 max 项的 i 为 s，产生答案的 min 项的 i 为 t。
考虑在已知 s 和 t 的情况下怎么算答案。
先给出结论，答案会是 a_s-a_s \operatorname{and} a_t。
至于原因，我们对于每一位单独考虑（因为位与位之间无关）。
- 若 a_s 与 a_t 的第 i 位均为 1，显然 x 这一位是什么不要紧，此时贡献为 0；
- 若 a_s 与 a_t 的第 i 位均为 0，显然 x 这一位是什么也不要紧，此时贡献为 0；
- 若 a_s 的第 i 位为 0，a_t 的这一位为 1，贡献为 -2^i。x 这一位填 1 就能使贡献为 0；
- 若 a_s 的第 i 位为 1，a_t 的这一位为 0，x 这一位应该填 0，此时贡献为 2^i。
由此我们发现答案就是第4种情况的贡献和，即如下式子。
a_s-a_s \operatorname{and} a_t
回到题目，假设新插入的数为 v，则新的 s 与 t 只能是以下三种情况。
-
-
-
对于第一种情况，直接继承上一次的答案。
对于第二种，答案为以下式子。
\max_{i=1}^{\lvert a \rvert -1} {(v-v \operatorname{and} a_i)}
于是问题转化成维护给定 v，维护以下式子。
\min_{i=1}^{\lvert a \rvert -1} {(v \operatorname{and} a_i)}
这是一个经典问题，使用按位贪心即可解决。
具体地，只需要记录 f_S 表示 a 中是否有某个数的超集为 S 。
```cpp
void dfs(int S)
{
f[S]=1;
for(int i=0;i<=n;i++)
{
if(!(S&(1<<i)) && !(f[S^(1<<i)]))
dfs(S^(1<<i));
}
}
```
处理完 $f_S$ 后有如下代码计算$\min_{i=1}^{\lvert a \rvert -1} {(v \operatorname{and} a_i)}$。
```cpp
int now=(1<<22)-1;
for(int i=22;i!=-1;i--)
{
if((v&(1<<i))&&f[now^(1<<i)])
now^=1<<i;
}
ans=now&v;
```
大致的思路是对于 $v$ 的第 $i$ 位，如果为 $1$ 就看集合中有没有这一位是 $0$ ，且满足前面已经选择的要求（即 $now$ 所记录的）的数。
计算出结果直接代入式子即可。
第三种情况类似，即求以下式子。
$$\max_{i=1}^{\lvert a \rvert -1} {(a_i-v \operatorname{and} a_i)}$$
尝试变形，将位运算以外变成与只与 $v$ 相关的样子。
$$\max_{i=1}^{\lvert a \rvert -1} {(v \operatorname{or} a_i - v)}$$
这个变形是好理解的，从意义上来理解就是 $a_i$ 与 $v$ 中至少有一个是 $1$ 的位数减去 $v$ 上是 $1$ 的位数，即 $a_i$ 的这一位为 $1$，$v$ 的这一位为 $0$ 的位数。
即变成了求如下式子。
$$\max_{i=1}^{\lvert a \rvert -1} {(v \operatorname{or} a_i)}$$
需要维护子集，进行按位贪心。
于是这道题就做完了。
## CODE
稍微注意一下我的代码里面的 $n$ 不是题目里的意义，而是实际上的 $\log_2 n$。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1<<23;
int n;
bool mor[maxn];//超集的f
bool les[maxn];//子集的f
void dfs1(int x)
{
mor[x]=1;
for(int i=0;i<=n;i++)
{
if(!(x&(1<<i)) && !(mor[x^(1<<i)]))
dfs1(x^(1<<i));
}
}
void dfs2(int x)
{
les[x]=1;
for(int i=0;i<=n;i++)
{
if((x&(1<<i)) && !(les[x^(1<<i)]))
dfs2(x^(1<<i));
}
}
int t;
int tn;
int q;
int U;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&q);
tn=n;
n=__lg(n);
U=(1<<(n+1))-1;
for(int i=0;i<=U;i++)
les[i]=mor[i]=0;
int ans=0;
for(int i=1;i<=q;i++)
{
int v;
scanf("%d",&v);
v=(v+ans)%tn;
int now=U;
for(int i=n;~i;i--)
{
if((v&(1<<i))&&mor[now^(1<<i)])
now^=1<<i;
}
ans=max(ans,v-(now&v));
// printf("%d ",now&v);
now=0;
for(int i=n;~i;i--)
{
if(!(v&(1<<i))&&les[now|1<<i])
now|=1<<i;
}
ans=max(ans,(now|v)-v);
// printf("%d ",now|v);
dfs1(v);
dfs2(v);
printf("%d ",ans);
}
printf("\n");
}
return 0;
}
```
参考资料：
[NOIP模拟-----位运算](https://www.cnblogs.com/forever-/p/9736088.html)
[位运算](https://www.cnblogs.com/Mars-LG/p/0x01_bit.html)