結果

問題 No.1778 括弧列クエリ / Bracketed Sequence Query
ユーザー imsuck
提出日時 2025-08-17 21:09:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 135 ms / 2,000 ms
コード長 2,237 bytes
コンパイル時間 3,188 ms
コンパイル使用メモリ 292,072 KB
実行使用メモリ 20,536 KB
最終ジャッジ日時 2025-08-17 21:09:51
合計ジャッジ時間 9,990 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
    #define dbg(...) void()
    #define debug() if (false)
#else
namespace dbg::options {
    template<> constexpr bool trivial_string() { return true; }
} // namespace dbg::options
#endif

template<class F> struct y_comb_t {
    F f;
    template<class T> y_comb_t(T &&_f) : f(forward<T>(_f)) {}
    template<class... Args> decltype(auto) operator()(Args &&...args) {
        return f(/* ref */(*this), forward<Args>(args)...);
    }
};
template<class F> y_comb_t<decay_t<F>> y_comb(F &&f) { return {forward<F>(f)}; }

void solve() {
    int n, q;
    string s;
    cin >> n >> q >> s;
    int m = n / 2;
    stack<int> st;
    vector<basic_string<int>> g(m + 1);

    vector<int> lab(n + 1, m);
    vector<pair<int, int>> bounds(m);

    int id = 0;
    st.push(n);
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') {
            st.push(i);
            lab[i] = id++;
        } else {
            int other = st.top();
            st.pop();
            lab[i] = lab[other];
            bounds[lab[i]] = {other + 1, i + 1};
            g[lab[st.top()]] += lab[i];
        }
    }
    int time = 0;
    vector<int> in(m + 1), out(m + 1);
    const int L = __lg(m) + 1;
    vector up(L, vector(m + 1, -1));
    y_comb([&](auto &dfs, int v, int p = -1) -> void {
        up[0][v] = p;
        for (int l = 0; l + 1 < L && up[l][v] != -1; l++)
            up[l + 1][v] = up[l][up[l][v]];

        in[v] = time++;
        for (int c : g[v]) {
            dfs(c, v);
        }
        out[v] = time;
    })(m);
    auto anc = [&](int p, int v) {
        return p == -1 || (in[p] <= in[v] && out[v] <= out[p]);
    };
    auto lca = [&](int u, int v) {
        if (anc(u, v)) return u;
        if (anc(v, u)) return v;
        for (int l = L - 1; l >= 0; l--)
            if (!anc(up[l][u], v)) u = up[l][u];
        return up[0][u];
    };
    while (q--) {
        int x, y;
        cin >> x >> y, x--, y--;
        id = lca(lab[x], lab[y]);
        if (id == m) {
            cout << "-1\n";
            continue;
        }
        auto [l, r] = bounds[id];
        cout << l << " " << r << "\n";
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    solve();
}
0