#1148582 (C++23) No.3467 Bracket Warp

• 問題: No.3467 Bracket Warp
• ユーザー: hikikomori
• 提出日時: 2026-02-19 19:21:07
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 416 ms / 2,000 ms
• コード長: 4,043 bytes
• コンパイル時間: 7,250 ms
• コンパイル使用メモリ: 387,028 KB
• 実行使用メモリ: 52,720 KB
• 最終ジャッジ日時: 2026-02-28 13:09:59
• 合計ジャッジ時間: 19,303 ms
• ジャッジサーバーID （参考情報）: judge1 / judge7

ファイルパターン	結果
sample	AC * 2
other	AC * 25

ソースコード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<long long, long long>;
using vpll = vector<pll>;
using mint = modint1000000007;
const long double EPS = 1e-18;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);
template <class T>
inline T CHMAX(T& a, const T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
    return a = (a > b) ? b : a;
}

struct Brtree {
    ll n, log_n;
    vvll ch, par;
    vll depth, D, pos, sz, pid;
    Brtree(const string& S) {
        n = S.size() + 2;
        log_n = 22;
        ch.resize(n);
        par.assign(log_n, vll(n, 0));
        depth.assign(n, 0);
        D.assign(n, 0);
        pos.assign(n, 0);
        sz.assign(n, 0);
        pid.assign(n, 0);
        build(S);
    }

   private:
    void dfs(ll u) {
        sz[u] = ch[u].size() + 1;
        rep(i, ch[u].size()) {
            ll v = ch[u][i];
            depth[v] = depth[u] + 1;
            pos[v] = i + 1;
            if (u == 1) {
                D[v] = 0;
            } else {
                D[v] = D[u] + min(pos[v], sz[u] - pos[v]);
            }
            dfs(v);
        }
    }

    void build(const string& S) {
        string S_pr = "(" + S + ")";
        vll st;
        ll idx = 0;
        rep(i, S_pr.size()) {
            if (S_pr[i] == '(') {
                idx++;
                pid[i] = idx;
                if (!st.empty()) {
                    ll p = st.back();
                    par[0][idx] = p;
                    ch[p].push_back(idx);
                } else {
                    par[0][idx] = idx;
                }
                st.push_back(idx);
            } else {
                pid[i] = st.back();
                st.pop_back();
            }
        }

        depth[1] = 0;
        D[1] = 0;
        dfs(1);

        reps(k, 1, log_n) {
            rrep(i, idx) { par[k][i] = par[k - 1][par[k - 1][i]]; }
        }
    }

    ll advance(ll u, ll d) const {
        rep(k, log_n) {
            if ((d >> k) & 1) u = par[k][u];
        }
        return u;
    }

    ll get_lca(ll u, ll v) const {
        if (depth[u] < depth[v]) swap(u, v);
        u = advance(u, depth[u] - depth[v]);
        if (u == v) return u;
        repd(k, log_n) {
            if (par[k][u] != par[k][v]) {
                u = par[k][u];
                v = par[k][v];
            }
        }
        return par[0][u];
    }

   public:
    ll query(ll l, ll r) const {
        ll u = pid[l];
        ll v = pid[r];
        if (u == v) return 0;
        ll lca = get_lca(u, v);
        if (lca == u || lca == v) {
            return abs(D[u] - D[v]);
        } else {
            ll u_anc = advance(u, depth[u] - depth[lca] - 1);
            ll v_anc = advance(v, depth[v] - depth[lca] - 1);
            ll diff = abs(pos[u_anc] - pos[v_anc]);
            ll span = (lca == 1) ? diff : min(diff, sz[lca] - diff);
            return (D[u] - D[u_anc]) + (D[v] - D[v_anc]) + span;
        }
    }
};
void solve() {
    string S;
    ll Q;
    cin >> S >> Q;
    Brtree bt(S);
    while (Q--) {
        ll l, r;
        cin >> l >> r;
        cout << bt.query(l, r) << "\n";
    }
}
int main() {
    INIT;
    solve();
    return 0;
}