Tóm tắt đề bài

Cho một xâu \(S\) ban đầu rỗng. Thực hiện \(m\) lệnh thuộc hai loại:

• Loại 1 (\(T\)): Thêm xâu \(T\) (gồm 2 ký tự ( hoặc )) vào cuối xâu \(S\).
• Loại 2 (\(U\)): Quay lại trạng thái của xâu \(S\) trước khi thực hiện lệnh thứ \(U\).

Sau mỗi lệnh, yêu cầu tính trọng số của xâu \(S\) hiện tại. Trọng số được định nghĩa là số lượng ký tự ít nhất cần thay đổi (từ ( thành ) hoặc ngược lại) để xâu \(S\) trở thành một dãy ngoặc đúng.

Phân tích

1. Trọng số của một xâu ngoặc

Để một xâu ngoặc bất kỳ trở thành dãy ngoặc đúng, ta có thể sử dụng thuật toán tham lam với ngăn xếp (stack):

• Duyệt qua từng ký tự của xâu.
• Nếu gặp (, đẩy vào stack.
• Nếu gặp ) và stack không rỗng và đỉnh stack là (, ta loại bỏ cặp ngoặc này (vì chúng đã khớp).
• Ngược lại, nếu không khớp được, ta giữ lại các ký tự không thể khớp.

Sau khi duyệt hết xâu, ta sẽ còn lại một xâu có dạng: ))) ... ((( (gồm \(a\) dấu ) và sau đó là \(b\) dấu ().

• Để biến xâu này thành dãy ngoặc đúng, ta cần:
  • Thay đổi \(\lceil a/2 \rceil\) dấu ) thành (.
  • Thay đổi \(\lceil b/2 \rceil\) dấu ( thành ).
• Công thức trọng số: \(W = \lceil a/2 \rceil + \lceil b/2 \rceil\). Lưu ý rằng tổng số ngoặc luôn là số chẵn (vì mỗi lần thêm 2 ký tự), nên \(a+b\) luôn chẵn, dẫn đến việc chuyển đổi luôn khả thi.

2. Xử lý các lệnh

• Lệnh loại 1: Thêm 2 ký tự. Ta cần cập nhật trạng thái \((a, b)\) từ trạng thái trước đó.
• Lệnh loại 2: Đây là thao tác quay lại quá khứ. Ta có thể lưu trữ trạng thái \((a, b)\) của xâu sau mỗi bước \(i\) để truy xuất nhanh chóng.

Hướng giải quyết

Quản lý trạng thái

Gọi trạng thái tại bước \(i\) là một cặp pair<int, int> memo[i] = {a, b}, trong đó:

• \(a\): số lượng dấu ) dư thừa ở bên trái (không thể khớp với ( nào trước đó).
• \(b\): số lượng dấu ( dư thừa ở bên phải (chưa có dấu ) nào sau đó khớp vào).

Cập nhật trạng thái khi thêm xâu \(T\)

Giả sử trạng thái trước đó là \((a, b)\). Khi thêm xâu \(T\) có 2 ký tự:

• Nếu $T = $ ((: \(b \leftarrow b + 2\).
• Nếu $T = $ )):
  • Thử khớp dấu ) thứ nhất: Nếu \(b > 0\) thì \(b \leftarrow b - 1\), ngược lại \(a \leftarrow a + 1\).
  • Thử khớp dấu ) thứ hai: Nếu \(b > 0\) thì \(b \leftarrow b - 1\), ngược lại \(a \leftarrow a + 1\).
• Nếu $T = $ ():
  • Thử khớp dấu (: \(b \leftarrow b + 1\).
  • Thử khớp dấu ): Vì vừa thêm (, dấu ) này sẽ khớp ngay lập tức \(\rightarrow b \leftarrow b - 1\). Trạng thái \((a, b)\) không đổi.
• Nếu $T = $ )(:
  • Thử khớp dấu ): Nếu \(b > 0\) thì \(b \leftarrow b - 1\), ngược lại \(a \leftarrow a + 1\).
  • Thử khớp dấu (: \(b \leftarrow b + 1\).

Xử lý lệnh loại 2

Nếu lệnh thứ \(i\) yêu cầu quay về trước lệnh \(U\), trạng thái tại bước \(i\) đơn giản là trạng thái sau khi thực hiện lệnh \(U-1\).

Tính kết quả

Với trạng thái \((a, b)\), trọng số là:

• Nếu \(a=0\) hoặc \(b=0\): \(W = \max(a, b) / 2\). (Thực tế là \((a+1)/2 + (b+1)/2\) vẫn đúng do tính chất chẵn lẻ).
• Tổng quát: \(W = \lfloor (a+1)/2 \rfloor + \lfloor (b+1)/2 \rfloor\).

Độ phức tạp

• Thời gian: \(O(m)\) do mỗi lệnh chỉ xử lý trong \(O(1)\) hoặc \(O(|T|)\).
• Bộ nhớ: \(O(m)\) để lưu trữ mảng memo chứa trạng thái tại mỗi bước.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 1000005;

// memo[i] lưu cặp {a, b} sau lệnh thứ i
// a: số dấu ')' dư, b: số dấu '(' dư
pair<int, int> memo[MAXN];
int pos[MAXN]; // pos[i] trỏ đến chỉ số trong memo của lệnh i

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int m;
    cin >> m;

    for (int i = 1; i <= m; ++i) {
        string s;
        cin >> s;

        if (s[0] == '(' || s[0] == ')') {
            // Lệnh loại 1: Thêm xâu T
            int prev_idx = pos[i - 1];
            int a = memo[prev_idx].first;
            int b = memo[prev_idx].second;

            // Xử lý từng ký tự trong xâu T
            for (char c : s) {
                if (c == '(') {
                    b++;
                } else { // c == ')'
                    if (b > 0) b--;
                    else a++;
                }
            }

            memo[i] = {a, b};
            pos[i] = i;
        } else {
            // Lệnh loại 2: Quay lại trước lệnh U
            int u = stoi(s);
            pos[i] = pos[u - 1];
        }

        // Tính trọng số từ trạng thái hiện tại {a, b}
        int cur_a = memo[pos[i]].first;
        int cur_b = memo[pos[i]].second;

        // Công thức tính số lần đổi ít nhất: ceil(a/2) + ceil(b/2)
        int ans = (cur_a + 1) / 2 + (cur_b + 1) / 2;
        cout << ans << "\n";
    }

    return 0;
}