Đặt

$$f(i) = \begin{cases} 0 & , i = 0 \\ f(i-1) + 1 &, s_i = \texttt{( } \text{ and } i > 0 \\ f(i-1) - 1 &, s_i = \texttt{) } \text{ and } i > 0 \\ \end{cases}$$

Với mỗi truy vấn ~l, r~, gọi:

• ~j~ là vị trí thuộc đoạn ~[l; r]~ mà ~f(j)~ nhỏ nhất.

• ~L~ là vị trí lớn nhất không quá ~l~ mà ~f(L) = f(j)~

• ~R~ là vị trí nhỏ nhất không nhỏ hơn ~r~ mà ~f(R) = f(j)~.

• Nếu không tìm được ~L, R~, đáp án là ~-1~. Ngược lại, đáp án là ~L~ ~R~.

Sử dụng set để lưu các vị trí ứng với từng giá trị của mảng ~f~, hỗ trợ tìm ~L, R~ trong ~O(\log n)~.

ĐPT: ~O(n\log n)~

Code mẫu

#include <iostream>
#include <set>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;
const int N = 4e5 + 5;
const int os = 2e5;

set <int> pos[N];

string s;

int T[N][20];
int a[N];
int n,q;

int getmin(int l, int r) {
    int d = log2(r - l + 1);
    return min(T[l][d], T[r - (1 << d) + 1][d]);
}   

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    cin >> s;
    for (int i = 1; i <= n; i++)
        a[i] = a[i - 1] + ((s[i - 1] == '(') ? 1 : -1);

    for (int i = 0; i <= n; i++)
        pos[a[i] + os].insert(i);

    for (int i = 0; i <= n; i++) {
        T[i][0] = a[i];
    }

    for (int j = 1; j < 20; j++)
    for (int i = 0; i + (1 << j) - 1 <= n; i++) {
        T[i][j] = min(T[i][j - 1], T[i + (1 << (j - 1))][j - 1]);
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        int mn = getmin(l - 1, r);
        auto lit = pos[mn + os].upper_bound(l - 1);
        if (lit == pos[mn + os].begin()) {
            cout << "-1\n";
            continue;
        }
        auto rit = pos[mn + os].lower_bound(r);
        if (rit == pos[mn + os].end()) {
            cout << "-1\n";
            continue;
        }
        cout << (*(--lit)) + 1 << " " << (*rit) << "\n";
    }
    return 0;
}