# D - Substr Swap [문제 링크](https://atcoder.jp/contests/abc419/tasks/abc419_d) ## Problem Statement You are given length-$N$ lowercase English strings $S$ and $T$, and $M$ pairs of integers $(L_1,R_1),(L_2,R_2),\ldots,(L_M,R_M)$. Perform the following operation for $i=1,2,\ldots,M$ in order: - Swap the $L_i$-th through $R_i$-th characters of $S$ and the $L_i$-th through $R_i$-th characters of $T$. - For example, if $S$ is `abcdef`, $T$ is `ghijkl`, and $(L_i,R_i)=(3,5)$, then $S$ and $T$ become `abijkf` and `ghcdel`, respectively. Find the string $S$ after performing the $M$ operations. ## Constraints - $1 \le N \le 5 \times 10^5$ - $1 \le M \le 2 \times 10^5$ - Each of $S$ and $T$ is a length-$N$ lowercase English string. - $1 \le L_i \le R_i \le N$ - $N, M, L_i, R_i$ are integers. ## Input The input is given from Standard Input in the following format: $N$ $M$ $S$ $T$ $L_1\ R_1$ $L_2\ R_2$ $\vdots$ $L_M\ R_M$ ## Output Output the $S$ after performing the $M$ operations. ## 풀이 #### Imos Method를 이용해 뒤집는 시작 위치와 마지막 위치를 기록해두고, 한번에 쓸면서 몇 번 뒤집혔는지 확인해주었다. ``` c++ #include<bits/stdc++.h> using namespace std; int swapped[500'001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; string s, t; cin >> n >> m >> s >> t; while(m--) { int l, r; cin >> l >> r; swapped[l-1]++; swapped[r]--; } for(int i=0;i<n;i++) { if(swapped[i]%2==0) cout << s[i]; else cout << t[i]; swapped[i+1] += swapped[i]; } } ```