ABC419 D

_std_O2 · 2025-08-17 16:03:51 · 题解

简要题意

给定两个长度为 N 的小写英文字符串 S 和 T，以及 M 对整数 (L_1, R_1), (L_2, R_2), \ldots, (L_M, R_M)。

操作规则

按顺序依次执行以下操作（i = 1, 2, \ldots, M）：

• 交换子串：将 S 中从第 L_i 到第 R_i 的字符与 T 中相同位置的字符互换。
  • 示例：
    若 S = \text{abcdef}，T = \text{ghijkl}，且 (L_i, R_i) = (3, 5)，则操作后：

输出所有 M 次操作完成后字符串 S 的最终结果。

分析

和简单题不能说很相似，只能说一模一样，纯纯树状数组板子题。

维护 tag 进行区间异或，最后单点查就行了，具体看代码。

Code

#include<iostream>
using namespace std;
const int N=3e6+6;
bool a[N],c[N],tag[N];
int n,m;
int lowbit(int x){
    return x&(-x);
}
int ask(int x){
    bool sum=0;
    for(int i=x;i<=n;i+=lowbit(i))
        sum^=tag[i];
    return sum;
}
void change(int l,int r,int k){
    for(int i=r;i;i-=lowbit(i))
        tag[i]^=k;
    for(int i=l-1;i;i-=lowbit(i))
        tag[i]^=k;
}
string s1,s2; 
int main(){

    cin>>n>>m;
    cin>>s1>>s2;
    for(int i=1;i<=m;i++){
        int x,y,k;
        cin>>x>>y;
        change(x,y,1);  
    }
    for(int i=1;i<=n;i++){
        if(ask(i)==1) cout<<s2[i-1];
        else cout<<s1[i-1];
    }
}