P11146 Strange Train Game 题解

· · 题解

思考过程写的有点长，但是做法是很好懂的。

字典序最大启发我们从大到小尝试钦定每一位是 1，然后判定其可行性，但是判定这部分好像很不好做。

我们先考虑有特殊性质的第二个 sub，这时候尝试从高到低贪心，你会发现我们的选择是唯一固定的，因为扫到每个节点的时候只可能最多有一种方式改变它的状态。

如何一般化？a_i \neq b_i 直接忽略不满足的点即可，再考虑所有左端点相同的区间的选择的影响，对于一个 i，假设其所有作为左端点的区间的右端点是 r_k（为了方便，这时的区间是左闭右开的，也就是实际上右端点是 r_k-1），这些端点分割出的区间集合的任意一个子集都能被表示。

所以其实你可以把这些区间等价转换成 [l,r_1],[r_1,r_2],[r_2,r_3] \cdots（注意还是左闭右开），然后只考虑 [l,r_1]，剩下的递归到后面处理。

注意到这样最后会剩下若干个左端点不同的区间，按 sub2 的方法做即可，但是这样消是平方的，不太妙（好像有不是平方的的证明，但我不是很会）。

考虑消区间的过程带来了什么性质，即如果你有 [l,r_1] 和 [l,r_2]，那 [r_1,r_2] 你也有。

这好像很能图论建模，考虑对每个 (l,r) 连边，可以得到对于一个 l 它最后消出来的右端点就是同一个联通快编号比它大的最小编号。

至此你只要并查集维护一下联通块并对每个点查一个后继即可，复杂度瓶颈是并查集，我赛时嫌麻烦写了两个 log 的 set 启发式合并，所以代码看个乐就好。

char a[N],b[N];
set<int> s,t[N];

int f[N],siz[N];

int find(int x){return (x==f[x]?x:f[x]=find(f[x]));}
void merge(int x,int y){
    x=find(x);y=find(y);if(x==y)return;
    if(siz[x]>siz[y])swap(x,y);
    siz[y]+=siz[x];f[x]=y;
    for(auto v:t[x])t[y].insert(v);
}

int c[N];

int main(){
    #ifdef EAST_CLOUD
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif
    int n=read(),m=read();
    scanf("%s",a+1);scanf("%s",b+1);
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i])s.insert(i);
    }
    if(!s.size()){
        cout<<(a+1);return 0;
    }
    for(int i=1;i<=n+1;i++)f[i]=i,siz[i]=1,t[i].insert(i);
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        if(l>(*s.rbegin()))continue;
        l=*(s.lower_bound(l));
        if(l>r)continue;
        auto it=s.upper_bound(r);
        if(it==s.end())r=n+1;
        else r=(*it);
        if(l>=r)continue;
        merge(l,r);
    }
    for(int i=1;i<=n;i++){
        c[i]^=c[i-1];
        if(a[i]==b[i]){putchar(a[i]);continue;}
        int now=(a[i]-'0')^(c[i]);
        if(now==1){putchar('1');continue;}
        int rt=find(i);
        auto it=t[rt].upper_bound(i);
        if(it==t[rt].end()){putchar('0');continue;}
        int r=(*it);
        c[i]^=1;c[r]^=1;
        putchar('1');
    }
    return 0;
}