题解：AT_abc419_d [ABC419D] Substr Swap

简单。

考虑一个

s

里的字符被交换

2k+1

次之后，就变成

t

里的对应的字符，

2k

次就变成原来的了。同理，

t

是类似的。只要维护更改的次数，用什么数据结构都行。这里使用的是树状数组。

时间复杂度

O((n+q) \log n)

。

AC Code：

CPP

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

题解：AT_abc419_d [ABC419D] Substr Swap

文章操作

相关推荐

评论

题解：AT_abc419_d [ABC419D] Substr Swap