[??记录]AT3969 [AGC025F] Addition and Andition
command_block
2021-05-18 07:56:14
**题意** ： 给定长度为 $n$ 的二进制数 $x$ 和长度为 $m$ 的 $y$ 。
对他们进行 $k$ 次以下操作 ：
- 令$z=x \ {\rm and} \ y$，并将 $x$ 和 $y$ 加上 $z$ 。
求出 $k$ 次操作后的 $x$ 和 $y$。
$n,m,k\leq 10^6$ ，时限$\texttt{2s}$。
------------
观察该操作的过程。
**从高位到低位**逐位查看，若 $x_i=y_i=1$ ，称发生一次“事件”，则将 $x_i,y_i$ 置为 $0$ ，在 $x_{i+1},y_{i+1}$ 处加一，并进位。
我们发现，对于发生对1事件的某个 $i$ ，后面低位的进位（权值和仅有 $2^i-1$）不可能跨越 $i$ 而影响到高位。
于是，低位的操作的“影响”永远不会追上高位操作的“影响”（影响是个偏序），可以先计算高位。
仍然考虑从高位到低位进行处理，先计算 $i$ 位及以上部分 $k$ 次操作后的结果，逐个加入低位。
加入一个低位时，不断尝试进行判定事件（可能向高位引发连锁反应），最多进行 $k$ 次则停止。
这个算法的复杂度仍然是 $O(nk)$ 的，尝试优化。
讨论可能的操作，并观察影响。
若 $x_i,y_i$ 同时 $+1$。
- ① 若 $x_i,y_i=0$ ，则消耗 $k$ 并发生一次事件，使得 $x_{i-1},y_{i-1}$ 加一。
- ② 若 $x_i=0,y_i=1$ ，则 $x_i\leftarrow 1,y_i\leftarrow 0$ ，令 $y_{i-1}$ 加一。
- ③ 若 $x_i=1,y_i=0$ ，则 $x_i\leftarrow 0,y_i\leftarrow 1$ ，令 $x_{i-1}$ 加一。
- ④ 若 $x_i=y_i=1$ ，则 $x_i,y_i\leftarrow 0$ ，令 $x_{i-1},y_{i-1}$ 加一。
若 $x_i$ 单独加一。（$y_i$ 单独加一类似）
- ⑤ 若 $x_i,y_i=0$ ，$x_{i-1}\leftarrow 1$ ，停止。
- ⑥ 若 $x_i=0,y_i=1$ ，则 $y_i\leftarrow 0$ ，消耗 $k$ 并发生一次事件，令 $x_{i-1},y_{i-1}$ 加一。
- ⑦ 若 $x_i=1$ ，则 $x_i\leftarrow 0$ ，令 $x_{i-1}$ 加一。
能够发现，对于 ⑤ ，一轮只会发生 $O(1)$ 次；对于 ④⑥⑦ ，会减少 $1$ 的数量；对于 ②③ ，使得双加状态变为单加状态，而想要回到双加状态，需要利用 ⑥ 而减少 $1$ 的数量。
综上，除情况 ① 之外，其余情况的发生次数均摊 $O(n)$。
对于情况 ① ，只需在操作时快速跳过连续的 $x_i=y_i=0$ 的段，可以用 `std::set` 维护。
总复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<set>
#define MaxN 2005000
using namespace std;
set<int> s2;
void mdf(int i,int k,char *x,char *y,bool op)
{
// op=1 Ϊ˫¼Ó£¬ op=2 Ϊµ¥¼Ó x
if (op==1){
if (x[i]==0&&y[i]==0){
if (!k){x[i]=y[i]=1;s2.insert(i);return ;}
set<int>::iterator it=s2.lower_bound(i);
if (it==s2.begin())mdf(i-k,0,x,y,1);
else {
it--;int p=*it;
if (p<=i-k)mdf(i-k,0,x,y,1);
else mdf(p,k-(i-p),x,y,1);
}
}
else if (x[i]==1&&y[i]==0){
x[i]=0;y[i]=1;
mdf(i-1,k,x,y,0);
}
else if (x[i]==0&&y[i]==1){
x[i]=1;y[i]=0;
mdf(i-1,k,y,x,0);
}
else {
x[i]=y[i]=0;s2.erase(i);
mdf(i-1,k,x,y,1);
}
}else {
if (x[i]==0&&y[i]==0)
{x[i]=1;s2.insert(i);}
else if (x[i]==0&&y[i]==1){
if (!k){x[i]=y[i]=1;return ;}
y[i]=0;s2.erase(i);
mdf(i-1,k-1,x,y,1);
}
else {
x[i]=0;
if (!y[i])s2.erase(i);
mdf(i-1,k,x,y,0);
}
}
}
void print(char *s,int n){
for (int i=0,fl=0;i<n;i++)
if (fl|=s[i])putchar(s[i]+'0');
puts("");
}
char x[MaxN],y[MaxN];
int m1,m2,n,k;
int main()
{
scanf("%d%d%d",&m1,&m2,&k);
int n=max(m1,m2)+k;
scanf("%s%s",x+n-m1,y+n-m2);
for (int i=n-m1;i<n;i++)x[i]-='0';
for (int i=n-m2;i<n;i++)y[i]-='0';
for (int i=0;i<n;i++)
if (x[i]||y[i])s2.insert(i);
for (int i=0;i<n;i++)
if (x[i]==1&&y[i]==1)
mdf(i,k-1,x,y,1);
print(x,n);print(y,n);
return 0;
}
```