题解：AT_abc419_d [ABC419D] Substr Swap

· · 题解

ABC419D Substr Swap - Solution

Problem Statement

给定两个长度均为 N 的字符串 S,T，有 M 次操作，每次给定 L_i,R_i，每次交换 S,T 的 [L_i,R_i]，求最终的 S。

Analysis

由于一直在 S,T 中交换子串，那么我们其实无需真正交换，只要更新一段区间被操作的次数即可。容易发现，只要某个字符被操作的次数是偶数，那么它不变，否则和 T 中的字符交换。

Approach

在分析后，发现只需要维护区间和的操作，容易想到差分，每次对 [L,R] 的操作就相当于 d[L]\gets d[L]+1,d[R+1]\gets d[R+1]-1，最后做前缀和并判断奇偶即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,d[N],sum[N];
string s,t;
int main(){
    cin>>n>>m>>s>>t;
    s=' '+s;
    t=' '+t;
    while(m--){
        int l,r;
        cin>>l>>r;
        d[l]++; //差分区间修改
        d[r+1]--;
    }
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+d[i]; //前缀和
        if(sum[i]%2) //按奇偶性判断是否要更改
            cout<<t[i];
        else
            cout<<s[i];
    }
    return 0;
}