CSES - Substring Reversals | Đảo ngược xâu con

Tác giả:

Dạng bài

Điểm: 2200 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một xâu, nhiệm vụ của bạn là xử lý các thao tác trong đó bạn đảo ngược một xâu con của xâu. Xâu cuối cùng sau tất cả các thao tác là gì?

Input

Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): độ dài của xâu và số lượng thao tác. Các ký tự của xâu được đánh số \(1, 2, \ldots, n\).
Dòng tiếp theo có một xâu độ dài \(n\) bao gồm các ký tự A–Z.
Cuối cùng, có \(m\) dòng mô tả các thao tác. Mỗi dòng có hai số nguyên \(a\) và \(b\): bạn đảo ngược một xâu con từ vị trí \(a\) đến vị trí \(b\).

Output

In xâu cuối cùng sau tất cả các thao tác.

Constraints

\(1 \leq n, m \leq 2 \cdot 10 ^ 5\)
\(1 \leq a, b \leq n\)

Example

Sample input

7 2
AYBABTU
3 4
4 7

Sample output

AYAUTBB

Bình luận

-2

Cái này là câu cuối của đề Lam Sơn

#include <bits/stdc++.h>
#define ll long long
const int N=1e6+3;
using namespace std;
ll n,a,b,dem=0,t,f[N];
string st;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    freopen("Daoxau.inp","r",stdin);
    freopen("daoxau.out","w",stdout);
    cin >> st;
    cin >> t;
    while(t--)
    {
        cin >> n;
        f[st.size()-n]++;
    }
    for(ll i=0;i<st.size()/2;i++)
    {
        f[i]=f[i]+f[i-1];
        if(f[i]%2==1)swap(st[i],st[st.size()-i-1]);
    }
    cout << st;
    return 0;
}

3 bình luận nữa