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

CPP

#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;
}

题解：AT_abc419_d [ABC419D] Substr Swap

文章操作

ABC419D Substr Swap - Solution

Problem Statement

Analysis

Approach

Code

相关推荐

评论

题解：AT_abc419_d [ABC419D] Substr Swap