题解：AT_abc419_d [ABC419D] Substr Swap

· · 题解

简单。

考虑一个 s 里的字符被交换 2k+1 次之后，就变成 t 里的对应的字符，2k 次就变成原来的了。同理，t 是类似的。只要维护更改的次数，用什么数据结构都行。这里使用的是树状数组。

时间复杂度 O((n+q) \log n)。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int N=500009;
int bit[N],n,m;
string s,t;
int LSB(int x){return x&(-x);}
void add(int x,int k){
    while(x<=n){
        bit[x]+=k;
        x+=LSB(x);
    }
}
int psq(int x){
    int ans=0;
    while(x>0){
        ans+=bit[x];
        x-=LSB(x);
    }
    return ans;
}
int main(){
    cin>>n>>m;
    cin>>s>>t;
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        add(l,1);
        add(r+1,-1);
    }
    for(int i=0;i<n;i++)
        s[i]=(psq(i+1)%2?t[i]:s[i]);
    cout<<s<<endl;
    return 0;
}