Đảo ngược xâu con

Tác giả:

Dạng bài

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

Cho một xâu \(S\) có độ dài \(l\) gồm các chữ cái thường. Cho \(Q\) thao tác, mỗi thao tác chỉ gồm một số nguyên dương \(x\), yêu cầu đảo ngược xâu con từ vị trí \(x\) đến vị trí \(l−x+1\). Chú ý: xâu kí tự được đánh số từ 1 đến \(l\).

Input

Dòng đầu tiên gồm một xâu \(S\) \((1 \leq l \leq 2 \times 10^5)\);
Dòng thứ hai gồm một số nguyên dương \(Q\) là số thao tác đảo ngược \((Q \leq 10^5)\).
Dòng thứ ba gồm \(Q\) số nguyên \(x_i\) \((1 \leq x_i \leq l )\)

Output

In ra xâu cuối cùng, sau khi thực hiện \(Q\) thao tác.

Example

Test 1

Input

tinteen
3
1 1 3

Output

tietnen

Note

Truy vấn 1: đảo ngược từ vị trí 1 đến 7: neetnit.
Truy vấn 2: đảo ngược từ vị trí 1 đến 7: tinteen.
Truy vấn 3: đảo ngược từ vị trí 3 đến 5: tietnen.

Bình luận

7
longkold00 7:48 p.m. 15 Tháng 10, 2021
Mình sẽ chia sẻ hướng làm của mình: ở bài này thứ tự đảo chuỗi sẽ không làm ảnh hưởng kết quả, mà phải là số lần đảo

Đầu tiên chúng ta sẽ quy hết các giá trị x>s.size/2 về xi=s.size-xi+1. Như vậy lúc này việc đảo chuỗi con sẽ bắt đầu từ lõi (x lớn nhất) sẽ đc đặt = 1 biến head

chúng ta sẽ tạo hàm con để swap 2 kí tự.

sử dụng đếm phân phối m[xi] để biết số lần xuất hiện của xi

Chúng ta sẽ xử lý từ vị trí head theo nguyên tắc:

4.1 nếu Q%2 là chẵn thì ta gán Q-=m[i] và bỏ qua

4.2 Nếu Q%2 là lẻ, ta đảo ngược xâu con từ i->j ( j gần nhất >i ) và gán Q-=m[i]

NOTE: Riêng với vị trí head đầu tiên chúng ta sẽ swap từ head->s.size/2

đây là code cho các bạn alt + f4 :> cứ tưởng x<s.size lúc đầu nên sai liên tục :))))

3

VoBaThongL921 8:58 p.m. 15 Tháng 10, 2021

em lấy substring thì bị tle test 3 luôn:)

4

longkold00 9:51 p.m. 15 Tháng 10, 2021

Bài này bắt mình đảo theo thứ tự á,e cứ viết ra giấy sẽ hiểu hơn. Việc đảo x=1 2 3 cũng chính là x=4 :v

4 bình luận nữa