题解：AT_abc419_d [ABC419D] Substr Swap

题意

给定了两个小写字符串 $s$ 和 $t$ ，输入 $m$ 次 $l_i$ ， $r_i$ ，将 $l$ 到 $r$ 之间的字符串进行替换。

思路

这一题大部分人的第一反应是模拟，但是大部分人都会超时，不知道那小部分人是怎么过的。于是就使用了差分。

差分是个什么

差分用来干什么

差分是一个可以快速的区间操作，即可以对一个数组的一个区间都加或减去一个数的数组。

差分怎么实现

对于差分数组的每一位 $d_i$ ，使它等于 $a_i-a_{i-1}$ ，如果在区间。这就是个差分数组。
当你要对 $i$ 到 $j$ 这一区间加上一个数 $x$ 时，只需让 $d_{i}+x$ ， $d_{j+1}-x$ 就可以了。

最后怎么让差分变回原数组

我们只需要求一个前缀和，即 $a_i=a_{i-1}+d_i$ 就是对应的数值了。

差分怎么在这题中使用

我们知道了理念，就可以在 $l$ 到 $r$ 之间加一，最后在求出原数组是判断它是不是偶数，是偶数输出对应的 $s_i$ 否则输出 $t_i$ 。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,m,d[500005],su;
string s,t;
string ans;
int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
    	int l,r;
        cin>>l>>r;
    	d[l]++;//求差分。
        d[r+1]++;
	}
	for(int i=1;i<=n;i++){
		su+=d[i];//复原原数组。
		if(su%2)ans+=t[i-1];//判断是否偶数。
		else ans+=s[i-1];
	}
	cout<<ans;
    return 0;
}

AC记录。
话说这道题怎么比上一题简单呢？
还有，管理大大求过。