[1705C] Mark and His Unfinished Essay

난이도: 1400

 

태그

• Recursion (재귀)
• String (문자열)

 

풀이

1. 쿼리로 들어온 \( k \)가 \( 1 \le k \le n \)이라면?

자명하게, 입력받은 문자열의 \( k \)번째 문자, 즉 \( S_k \)가 정답이 됩니다.

 

2. 쿼리로 들어온 \( k \)가, \( x \)번째 쿼리에서 추가된 글자라면?

\( x \)번째 쿼리를 아래와 같이 나타내봅시다.

\( s_1, e_1, s_2, e_2 \): \( S \)의 \( [s_1, e_1] \)번째 글자를 \( [s_2, e_2] \)에 붙여넣는다.

(이 때, \( s_2 = |S| + 1, e_2 = |S| + (e_1-s_1+1) \)이 됩니다.)

 

\( k \)번째 글자가 \( x \)번째 쿼리에서 추가된 글자라면, \( s_2 \le k \le e_2 \)입니다.

이 글자들은 \( [s_1, e_1] \)에서 추가된 글자들이므로, 이를 \( s_1 \le k' \le e_1 \)으로 변환해서 풀어볼 수 있습니다.

 

이 때의 \( k' \)은, \( s_2 \)를 \( s_1 \)으로 변환시키면 되므로 \( k' = k - s_2 + s_1 \)이 됩니다.

 

코드

위에서 설명한 걸, 마지막 연산부터 시작해서 역순으로 검사해주면 됩니다.

\( k \)가 \( x \)번째 쿼리에서 추가된 글자가 아니면 그냥 패스해주면 됩니다.

pl4 arr[50];
 
void Main(){
    int t; cin >> t; while (t--){
        string s; ll sl; int n, q; cin >> sl >> n >> q >> s;
        s = " " + s;
        for (int i = 1; i <= n; i++){
            ll l, r; cin >> l >> r; ll len = r-l+1;
            arr[i] = { {sl+1, sl+len}, {l, r} };
            sl += len;
        }
        while (q--){
            ll idx; cin >> idx;
            for (int i = n; i >= 1; i--){
                if (arr[i].fr.fr <= idx && idx <= arr[i].fr.sc){
                    idx -= arr[i].fr.fr - arr[i].sc.fr;
                }
            }
            cout << s[idx] << endl;
        }
    }
}