Atcoder agc025F

做了几天也不会，最后弃疗看了题解。其实做法大概和题解差不多的，就是没想到势能分析后暴力复杂度是对的。。。
对于某一位，任意时刻两个数的值可能有四种状态（$00$，$01$，$10$，$11$）。
考虑从低位往高位依次处理进位关系。假设我们当前处理到某一位，依次维护了更低的位对这一位进位的状态（$01$，$10$，$11$）和时间。一个显然的暴力是依次处理所有的操作，并且求出对更高的位的进位以及这一位最后的结果，注意如果我们某一位初始时或经过某次操作后状态是$11$，那么可以直接把状态变成$00$并且下一位增加一个$11$的进位，所以我们分析的时候不考虑$11$状态。
可惜这个复杂度显然是假的，因为连续的一段$11$进位到下一层也是相同长度的连续一段$11$。
仔细思考一下，我们可以给出如下优化后的算法：对于$01$或$10$操作直接模拟，将连续的$11$操作用链表缩起来。对于一段$11$操作，如果操作前这一位的状态为$00$，那么会对下一位仍然连续做相同长度的$11$进位，可以直接计算贡献并得到下一层一个新的$11$连续段；如果是$01$或$10$，我们将链表拆开模拟，会对下一位交替做$01$和$10$的进位。
如何分析这个算法的复杂度呢？我们考虑每个位处理的过程，对每个$01$和$10$操作带$3$的势能，每个$11$操作带$4$的势能，且当前状态每个$1$的位也带上$2$的势能。那么考虑遍历过程，如果遇到一个$01$或$10$操作，不论操作前状态是哪个，操作后总势能必定减小$1$，代价被支付了。如果遇到一段连续的$11$操作，如果不拆开（操作前状态是$00$），那么实际代价是$\mathcal{O}(1)$，势能不变，在下一位有相同长度的$11$进位，此时若是非平凡情况，那么由于下一个操作必为$01$或$10$，可以用它减小的势能支付；如果拆开（操作前状态是$01$或$10$），操作后状态势能不变，且遍历拆开的代价被由$11$操作变为$01$或$10$操作减小的势能支付了。
初始势能只会由每个位初始时的势能带来，且最后答案的位数是$\mathcal{O}(N+M+K)$的，于是均摊的时间复杂度为$\mathcal{O}(N+M+K)$。

#include <bits/stdc++.h>
#define last last2
#define FR first
#define SE secondusing namespace std;typedef pair<int,int> pr;int val[10000005],pre[10000005];
int head[2000005],tail[2000005];
int dis[2000005],leng[2000005];
int cnt,tot;pr num[2000005];
int len;int insert(int st,int k) {
    static pr cur[2000005];static int curhead[2000005],curtail[2000005];static int curleng[2000005],curdis[2000005];if (st==1||st==2) {
    for(int i=len;i>0;i--) num[i+1]=num[i];num[1]=pr(0,st);len++;} else if (st==3) {
    for(int i=len;i>0;i--) num[i+1]=num[i];num[1]=pr(0,st);len++;for(int i=cnt;i>0;i--) {
    head[i+1]=head[i];tail[i+1]=tail[i];leng[i+1]=leng[i];dis[i+1]=dis[i];}cnt++;head[1]=tail[1]=++tot;leng[1]=1;dis[1]=0;}st=0;int sz1=0,sz2=0,r=1;bool v=0;for(int i=1;i<=len;i++) {
    if (num[i].SE<=2) {
    if (!st) st=num[i].SE;else if (st==num[i].SE) {
    cur[++sz1]=num[i];st=0;}else {
    cur[++sz1]=pr(num[i].FR+1,3);sz2++;curhead[sz2]=curtail[sz2]=++tot;curleng[sz2]=1;curdis[sz2]=0;st=0;if (num[i].FR==k) v=1;}} else {
    if (!st) {
    cur[++sz1]=pr(num[i].FR+1,3);sz2++;curhead[sz2]=head[r];curtail[sz2]=tail[r];curleng[sz2]=leng[r];curdis[sz2]=dis[r];if (num[i].FR+dis[r]==k) v=1;}else {
    if (leng[r]&1) st=3-st;int d=num[i].FR+dis[r],nst=st,last=sz1;for(int j=tail[r];j;j=pre[j]) {
    nst=3-nst;cur[++sz1]=pr(d,nst);d-=val[j];} reverse(cur+last+1,cur+sz1+1);}r++;}}len=sz1;cnt=sz2;for(int i=1;i<=len;i++) num[i]=cur[i];for(int i=1;i<=cnt;i++) {
    head[i]=curhead[i];tail[i]=curtail[i];leng[i]=curleng[i];dis[i]=curdis[i];}return (!v)?st:3-st;
}void merge(int k) {
    static pr cur[2000005];static int curhead[2000005],curtail[2000005];static int curleng[2000005],curdis[2000005];if (num[len].SE<3) {
    if (num[len].FR>k) len--;}else {
    if (num[len].FR+dis[cnt]>k) {
    leng[cnt]--;dis[cnt]-=val[tail[cnt]];tail[cnt]=pre[tail[cnt]];}if (!leng[cnt]) {
    len--;cnt--;}}int sz1=0,sz2=0,r=1;for(int i=1;i<=len;i++)if (i==1||num[i].SE!=3||cur[sz1].SE!=3) {
    cur[++sz1]=num[i];if (num[i].SE==3) {
    sz2++;curhead[sz2]=head[r];curtail[sz2]=tail[r];curleng[sz2]=leng[r];curdis[sz2]=dis[r];r++;}}else {
    pre[head[r]]=curtail[sz2];val[head[r]]=num[i].FR-(cur[sz1].FR+curdis[sz2]);curtail[sz2]=tail[r];curleng[sz2]+=leng[r];curdis[sz2]+=dis[r]+val[head[r]];r++;}len=sz1;cnt=sz2;for(int i=1;i<=len;i++) num[i]=cur[i];for(int i=1;i<=cnt;i++) {
    head[i]=curhead[i];tail[i]=curtail[i];leng[i]=curleng[i];dis[i]=curdis[i];}
}char s1[1000005],s2[1000005];
bool ans1[2000005],ans2[2000005];int main() {
    int n,m,k;scanf("%d%d%d",&n,&m,&k);scanf("%s%s",s1+1,s2+1);reverse(s1+1,s1+n+1);reverse(s2+1,s2+m+1);for(int i=1;i<=max(n,m);i++) {
    int st=0;if (s1[i]=='1'&&s2[i]=='1') st=3;else if (s1[i]=='1') st=1;else if (s2[i]=='1') st=2;st=insert(st,k);ans1[i]=((st==1||st==3)?1:0);ans2[i]=((st==2||st==3)?1:0);merge(k);}int d1=max(n,m),d2=max(n,m);while (len) {
    int st=insert(0,k);ans1[++d1]=((st==1||st==3)?1:0);ans2[++d2]=((st==2||st==3)?1:0);merge(k);}while (!ans1[d1]) d1--;for(int i=d1;i>0;i--) putchar((ans1[i])?'1':'0');printf("\n");while (!ans2[d2]) d2--;for(int i=d2;i>0;i--) putchar((ans2[i])?'1':'0');printf("\n");return 0;
}