\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• Điều kiện để đoạn \([l, r]\) với các giá trị \(\big(\) \(s_l, s_{l+1}, \dots, s_r\) \(\big)\) là dãy ngoặc đúng ngắn nhất cố định từ ngoặc mở "(" ở \(l\) hoặc ngoặc đóng ")" ở \(r\) (không xét kí tự ở giữa), là:

Đoạn có ít nhất 2 dấu ngoặc, tổng số ngoặc phải là chẵn

Số lượng ngoặc mở bằng với số lượng ngoặc đóng

Với mỗi ngoặc mở, có một ngoặc đóng tương ứng

• Dựa trên 3 điều kiện trên, ta có nhận xét như sau

Nhặc lại rằng hoặc là vị trí \(l\) cố định ngoặc mở hoặc \(r\) cố định ngoặc đóng

Gọi \(cnt(l, r)\) là hiệu số lượng ngoặc mở trừ đi số lượng ngoặc đóng trong đoạn \([l, r]\)

Gọi \(v_p = cnt(p, n)\) là hiệu số lượng ngoặc mở trừ số lượng ngoặc đóng kể từ \(p\) qua phải (hậu tố)

[1] Khi \(v_{l-1} = v_{r}\) thì ta có \(v_{l-1} - v_{r} = 0\), có nghĩa là đoạn \([l, r]\) có số lượng ngoặc là chẵn và số lượng ngoặc mở bằng số lượng ngoặc đóng

[2] Khi \(min(v_l, v_{l+1}, \dots, v_{r-1}) > v_{l-1}\) thì ta có số lượng ngoặc mở luôn không bé hơn số lượng ngoặc đóng trong mọi đoạn tiền tố \([l, l], [l, l + 1], \dots, [l, r -1], [l, r]\)

Khi cả [1] và [2] thỏa mãn thì cũng suy ra được số lượng ngoặc đóng không lớn hơn số lượng ngoặc mở trong mọi đoạn hậu tố \([r, r], [r - 1, r], \dots, [l + 1, r], [l, r]\)

Mà từ [1] cũng có số lượng ngoặc mở bằng số lượng ngoặc đóng nên từ đó suy ra mỗi ngoặc mở đều có một ngoặc đóng tương ứng

• Vậy khi người ta cho vị trí \(p\) và \(c\) là dấu ngoặc mở thì ta xét \(p\) như \(l\) và tìm vị trí \(r\) nhỏ nhất bên phải \(l\) thỏa mãn 2 điều kiện trên

• Vậy khi người ta cho vị trí \(p\) và \(c\) là dấu ngoặc đóng thì ta xét \(p\) như \(r\) và tìm vị trí \(l\) lớn nhất bên trái \(r\) thỏa mãn 2 điều kiện trên

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Để tiện, ta sẽ định nghĩa hàm \(f()\) như sau

\(f(s_i) = 0\) khi \(s_i\) không phải là dấu ngoặc

\(f(s_i) = +1\) khi \(s_i\) là dấu ngoặc mở "("

\(f(s_i) = -1\) khi \(s_i\) là dấu ngoặc đóng ")"

• Từ đó ta định nghĩa mảng \(a[]\) có \(a_i = f(s_i)\ \ \forall\ \ i = 1 \dots |s|\)

• Ta dùng cấu trúc dữ liệu có thể trả lời các truy vấn sau

Hàm modify(l, r, v) Cộng vào một đoạn \([l \dots r]\) mỗi số \(a_x\) một giá trị bằng \(v\)

Hàm query(l, r) Tính min \(a_l, a_{l+1}, \dots, a_{r-1}, a_r\)

Hàm solve(p): Cố định tại \(l\), tìm vị trí \(n \geq r > l\) nhỏ nhất thỏa mãn đề hoặc trả về \(-1\) nếu không tồn tại

• Thay vì thêm việc tím kiếm \(l\) khi cố định \(r\), ta có thể đơn giản là lât ngược xâu lại và dùng cấu trúc dữ liệu trên xâu đó

Ta có thể tạo một xâu đảo ngược và dùng cấu trúc dữ liệu thứ hai lên nó xem như là đã bỏ qua việc lật xâu \(O(n)\)

• Để tiện, từ đây ta định nghĩa

\(a[], p, c, v, T\) lần lượt là mảng \(a[]\) của xâu gốc, truy vấn tại điểm \(p\) kí tự \(c\) có giá trị \(v = f(c)\) và cấu trúc dữ liệu \(T\) thực hiện các hàm trên mảng \(a[]\)

\(inv\_a[], inv\_p, inv\_c, inv\_v, inv\_T\) lần lượt là mảng \(inv\_a[]\) của xâu đảo ngược, truy vấn tại điểm \(inv\_p = n - p + 1\) kí tự \(inv\_c\) có giá trị \(inv\_v = -v\), và cấu trúc dữ liệu \(inv\_T\) thực hiên các hàm trên mảng \(inv\_a[]\)

• Môi truy vấn nhận vị trí \(p\) và kí tự \(c\)

Gán giá trị \(v = f(c)\)

Xóa giá trị \(a[p]\) lần trước đi bằng T.modify(p, n, -a[p])

Gán giá trị \(a[p] = v\)

Thêm giá trị \(a[p]\) lần này vào bằng T.modify(p, v, +a[p])

Khi \(c\) là ngoặc mở thì thực hiện truy vấn res = T.solve(p)

• Tương tự với xâu đảo ngược

Xóa giá trị \(inv\_a[inv\_p]\) lần trước đi bằng inv_T.modify(inv_p, n, -inv_a[inv_p])

Gán giá trị \(inv\_a[inv\_p] = inv\_v\)

Thêm giá trị \(inv\_a[inv\_p]\) lần này vào bằng inv_T.modify(inv_p, n, -inv_a[inv_p])

Khi \(c\) là ngoặc đóng thì thực hiên truy vấn inv_res = inv_T.solve(p)

Lưu ý rằng ta phải đảo ngược vị trí \(res = n - inv\_res + 1\) khi \(inv\_res \neq -1\) vì xâu đã được lật ngược

\(\color{purple}{\text{Độ phức tạp}}\)

• Có \(m\) truy vấn, mỗi truy vấn mất \(O(f(x))\) thời gian, trong đó

Nếu sài trâu thì ta có \(O(f(x)) = O(n)\) vì cùng lắm phải duyệt qua cả đoạn văn bản

Nếu sài cấu trúc dữ liệu cây phân đoạn lan truyền lười nhác (segment tree lazy propagation) thì chỉ còn \(O(n log^3 n)\) đến \(O(n log n)\)

\(\color{green}{\text{Code tham khảo }}\): Cấu trúc dữ liệu đặc biệt (Segment Tree Lazy Propagation), Cài đặt

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(m log^2 n)\ \color{purple}{\text{thời gian}}\ ||\ O(n + m)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int LIM = 1e5 + 15;
const int INF = 0x3f3f3f3f;

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

struct Node 
{
    /// Property
    int val, lazy;
    Node (int val = 0, int lazy = 0)
    : val(val), lazy(lazy) {}

    /// lazy update
    void update(int v)
    {
        val += v;
        lazy += v;
    }
};

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

/// Property:
/// * Minimal Prefixsum in any range
/// * Hold the value 
///
/// Possibility:
/// * Range Addtion Modification: modify(l, r, v) -> a[x] += v | x = l -> r
/// * Range Minimum Query:        query(l, r)     -> min(a[l..r]) min(a[l], a[l + 1], .., a[r])
/// * Binary Search Solve:        solve(p)        -> { min(k)           (min(a[p..k-1]) > a[k-1] = a[p-1]) & (k = p -> n)
///                                                  { -1 if not exist
struct Lazy_Segment_Tree
{
    /// property
    int n;
    vector<Node> t;

    /// initialization
    void init(int lim)
    {
        for (n = 1; n < lim; n <<= 1);
        t.assign(n << 2, Node());
    }

    /// lazy update
    void push(int p)
    {
        if (t[p].lazy == 0) return ;
        t[p * 2 + 1].update(t[p].lazy);
        t[p * 2 + 2].update(t[p].lazy);
        t[p].lazy = 0;  
    }

    /// merge 2 children to parent
    void update(int p)
    {
        t[p].val = min(t[p * 2 + 1].val, t[p * 2 + 2].val);
    }

    /// Range Modify [l..r)
    void modify(int l, int r, int v, int ct, int lt, int rt)
    {
        if (lt >= r || l >= rt) return ;
        if (lt >= l && r >= rt)
        {
            t[ct].update(v);
            return ;
        }

        push(ct);
        int mt = (lt + rt) >> 1;
        modify(l, r, v, ct * 2 + 1, lt, mt);
        modify(l, r, v, ct * 2 + 2, mt, rt);
        update(ct);
    }

    /// Range Modify [l..r]
    void modify(int l, int r, int v)
    {
        return modify(l, r + 1, v, 0, 0, n);
    }

    /// Range Query [l..r)
    int query(int l, int r, int ct, int lt, int rt)
    {
        if (lt >= r || l >= rt) return +INF;
        if (lt >= l && r >= rt) return t[ct].val;

        push(ct);
        int mt = (lt + rt) >> 1;
        return min(query(l, r, ct * 2 + 1, lt, mt),
                   query(l, r, ct * 2 + 2, mt, rt));
    }

    /// Range Query [l..r]
    int query(int l, int r)
    {
        return query(l, r + 1, 0, 0, n);
    }

    /// binary search for first valid baracks 
    int solve(int p, int lim)
    {
        int res = +INF;
        int v = (p == 1) ? 0 : query(p - 1, p - 1);
        for (int l = p + 1, r = lim; l <= r; )
        {
            int m = (l + r) >> 1;
            if (query(p, m - 1) > v)
            {
                res = m;
                l = m + 1;
            }
            else 
            {
                r = m - 1;
            }
        }

        return (res > lim || query(res, res) != v) ? -1 : res;
    }
};

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n, q;
Lazy_Segment_Tree T, inv_T;

int a[LIM];
void update(int p, int v)
{
    T.modify(p, n, v);
    int inv_v = -v;
    int inv_p = n - p + 1;
    inv_T.modify(inv_p, n, inv_v);
}

int f(char c)
{
    if (c == '(') return +1;
    if (c == ')') return -1;
    return 0;
}

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    cin >> n >> q;

    memset(a, 0, sizeof(a));
    inv_T.init(n + 1);
    T.init(n + 1);
    while (q-->0)
    {
        int p;  char c;
        cin >> p >> c;

        int v = f(c);
        update(p, v - a[p]);
        a[p] = v;

        if (v == +1) /// "("
        {
            int res = T.solve(p, n);
            cout << res << '\n';
        }

        if (v == -1) /// ")"
        {
            int inv_p = n - p + 1;
            int inv_res = inv_T.solve(inv_p, n);
            cout << (inv_res == -1 ? -1 : n - inv_res + 1) << '\n';
        }    
    }

    return 0;
}