ABC419 D

简要题意

给定两个长度为

N

的小写英文字符串

S

和

T

，以及

M

对整数

(L_1, R_1), (L_2, R_2), \ldots, (L_M, R_M)

。

操作规则

按顺序依次执行以下操作（

i = 1, 2, \ldots, M

）：

交换子串：将 $S$ $S$ 中从第 $L_i$ $L_{i}$ 到第 $R_i$ $R_{i}$ 的字符与 $T$ $T$ 中相同位置的字符互换。
- 示例：
  若 $S = \text{abcdef}$ $S = abcdef$ ， $T = \text{ghijkl}$ $T = ghijkl$ ，且 $(L_i, R_i) = (3, 5)$ $(L_{i}, R_{i}) = (3, 5)$ ，则操作后：
  - $S$ 变为 abijkf（原 cde 替换为 ijk）
  - $T$ 变为 ghcdel（原 ijk 替换为 cde）

输出所有

M

次操作完成后字符串

S

的最终结果。

分析

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

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

Code

CPP

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

文章操作

简要题意

操作规则

分析

Code

相关推荐

评论

ABC419 D