#1558. BRACKET - Biến đổi dãy ngoặc

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Nguồn: Contest PVH 2021 - 2022

Dãy ngoặc là một dãy chỉ gồm các kí tự mở ngoặc ( và đóng ngoặc ). Dãy ngoặc đúng là một dãy ngoặc được xây dựng dựa trên quy tắc sau:

  • Dãy ngoặc rỗng là một dãy ngoặc đúng.
  • Nếu A là một dãy ngoặc đúng, thì ( A ) là một dãy ngoặc đúng.
  • Nếu A B là hai dãy ngoặc đúng thì AB cũng là dãy ngoặc đúng.

Ví dụ, (()), ()()()(()) là các dãy ngoặc đúng; còn )( hay (() thì không.

Bạn được cho một xâu kí tự s là một dãy ngoặc đúng cùng dãy q số p_1, p_2, \ldots, p_q . Bạn cần thực hiện lần lượt q thao tác. Tại thao tác thứ i , bạn cần làm những việc sau:

  • Thay đổi kí tự thứ p_i của s (từ ( sang ) hoặc ngược lại).
  • Tìm vị trí a_i là vị trí nhỏ nhất sao cho nếu thay đổi kí tự ở vị trí a_i (từ ( sang ) hoặc ngược lại) thì xâu kí tự s trở thành dãy ngoặc đúng.
  • In ra vị trí a_i vừa tìm được và thay đổi kí tự ở vị trí này.

Chú ý rằng, ở bất kì thao tác nào, bạn bắt đầu khi xâu s đang là dãy ngoặc đúng. Do đó, việc thay đổi kí tự thứ p_i khiến s bây giờ chắc chắn không phải dãy ngoặc đúng, và ta dễ dàng chứng minh được vị trí a_i cần tìm ở trên là luôn tồn tại. Khi thay đổi kí tự ở vị trí a_i , s trở lại là dãy ngoặc đúng.

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên n q (1 \leq n \leq 1000000, 1 \leq q \leq 600000) , lần lượt là độ dài của dãy ngoặc s và số thao tác bạn cần thực hiện;
  • Dòng thứ hai chứa xâu kí tự s là một dãy ngoặc đúng độ dài n ;
  • Dòng thứ ba chứa q số nguyên p_1, p_2, \ldots, p_q (1 \leq p_q \leq n) mô tả các thao tác cần thực hiện.

Dữ liệu ra:

  • In ra q số nguyên a_1, a_2, \ldots, a_q là các vị trí tìm được ở các thao tác. Các số cần được viết trên một dòng, ngăn cách với nhau bởi dấu cách.

Ví dụ:

Dữ liệu vào:

6 3
((()))
4 3 1

Dữ liệu ra:

2 2 1

Giải thích:

Trong ví dụ trên, ban đầu dãy ngoặc s ((())). Các thao tác diễn ra như sau:

  • Thao tác đầu tiên: Sau khi thay đổi kí tự ở vị trí p_1 = 4 , s trở thành (((()). Để s trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí a_1 = 2 . Khi đó s trở thành ()(()).
  • Thao tác tiếp theo: Sau khi thay đổi kí tự ở vị trí p_2 = 3 , s trở thành ())()). Để s trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí a_2 = 2 . Khi đó s trở thành (()()).
  • Thao tác cuối cùng: Sau khi thay đổi kí tự ở vị trí p_3 = 1 , s trở thành )()()). Để s trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí a_3 = 1 . Khi đó s trở thành (()()).

Giới hạn:

Bộ test của bài được chia làm các subtask như sau:

  • Subtask 1 ( 24\% số điểm): n \leq 500 q \leq 300 ;
  • Subtask 2 ( 26\% số điểm khác): n \leq 7000 q \leq 4200 ;
  • Subtask 3 ( 24\% số điểm khác): n \leq 200000 q \leq 120000 ;
  • Subtask 4 ( 26\% số điểm còn lại): n \leq 1000000 q \leq 600000 .