题解：AT_abc419_d [ABC419D] Substr Swap

Natural_Selection · 2025-08-20 13:00:29 · 题解

题解：AT_abc419_d Substr Swap

AtCoder

阿巴太菜 C 没过，但过了 D。

思路

首先，我们看到这字符串翻来翻去的，就知道，一定会有重复翻的。那一个字符串翻来翻去，有可能会翻会来，那我们就建一个数组来存储每一位翻转的次数就行了。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e5+1;
bitset<N>k;
string a,b;
int n,m;
signed main(){
    k.reset();
    cin>>n>>m;
    cin>>a>>b;
    while(m--){
        int l,r;
        cin>>l>>r;
        for(int i=l-1;i<r;i++){
            k[i]=k[i]^1;
        }
    }
    for(int i=0;i<n;i++){
        if(k[i]==1){
            swap(a[i],b[i]);
        }
    }
    cout<<a<<"\n";
    return 0;
}

结果丝毫不出意外，TLE 了……

我们要想办法把在 l 到 r 之间的赋值的时间复杂度降到 O(1)。

这个时候什么算法能胜任呢？很明显，答案是差分！

知道是差分，这题就好做了。

AC 代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e5+1;
int k2[N];
string a,b;
int n,m;
void f(int l,int r,int c){//差分
    k2[l-1]+=c;
    k2[r]-=c;
}
signed main(){
    cin>>n>>m;
    cin>>a>>b;
    while(m--){
        int l,r;
        cin>>l>>r;
        f(l,r,1);
    }
    for(int i=1;i<n;i++){
        k2[i]+=k2[i-1];
    }
    for(int i=0;i<n;i++){
        if(k2[i]%2==1){
            swap(a[i],b[i]);//如果翻转了奇数次，就交换
        }
    }
    cout<<a<<"\n";
    return 0;
}