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

• 問題: No.3467 Bracket Warp
• ユーザー: Nzt3
• 提出日時: 2026-03-06 21:33:40
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 327 ms / 2,000 ms
• コード長: 3,645 bytes
• コンパイル時間: 4,642 ms
• コンパイル使用メモリ: 365,244 KB
• 実行使用メモリ: 34,996 KB
• 最終ジャッジ日時: 2026-03-06 21:34:00
• 合計ジャッジ時間: 16,459 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

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

ソースコード

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define ov4(a, b, c, d, name, ...) name
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for (ll i = (a) - 1; i >= (b); i--)
#define fore(e, v) for (auto&& e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template <typename T, typename S>
bool chmin(T& a, const S& b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
bool chmax(T& a, const S& b) {
  return a < b ? a = b, 1 : 0;
}
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
  _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

pair<int,pii> seg_op(pair<int,pii> a,pair<int,pii> b) {
  if(a.first==b.first) return make_pair(a.first, pii{min(a.second.first,b.second.first),max(a.second.second,b.second.second)});
  else return min(a,b);
}
pair<int,pii> seg_e(){return make_pair(INF,pii{INF,-1});}

int main(){
  string S;
  cin>>S;
  S="("+S+")";
  int N=sz(S);
  vector<vector<pii>> G;
  G.reserve(N);
  vi toNode(N);
  stack<vi> child;
  vector<map<int,int>> cIdx(N);
  child.push(vi());
  rep(i,N){
    if(S[i]=='('){
      toNode[i]=sz(G);
      child.top().push_back(sz(G));
      G.push_back(vector<pii>());
      child.push(vi());
    }else{
      vi c=child.top();
      child.pop();
      toNode[i]=child.top().back();
      rep(j,sz(c)){
        cIdx[toNode[i]][c[j]]=j;
      }
      if(toNode[i]==0){
        rep(j,sz(c)){
          G[toNode[i]].push_back(pii{c[j],N*3});
        }
      }else{
        rep(j,sz(c)){
          G[toNode[i]].push_back(pii{c[j],min(j+1,sz(c)-j)});
        }
      }
    }
  }
  queue<int> bfs;
  N/=2;
  vi dist(N,INF),depth(N,INF);
  bfs.push(0);
  dist[0]=0;
  depth[0]=0;
  while(bfs.size()){
    int v=bfs.front();
    bfs.pop();
    for(auto [u,w]:G[v]){
      dist[u]=dist[v]+w;
      depth[u]=depth[v]+1;
      bfs.push(u);
    }
  }
  vi vin(N),vout(N),vord;
  vord.reserve(N*2);
  auto dfs_lca=[&](auto self,int v,int p) -> void {
    for(auto i:G[v]){
      vin[i.first]=sz(vord);
      vord.push_back(i.first);
      self(self,i.first,v);
    }
    vout[v]=sz(vord);
    vord.push_back(p);
  };
  vord.push_back(0);
  vin[0]=0;
  dfs_lca(dfs_lca, 0,-1);

  // for(auto i:vord)cerr<<i<<' ';
  // cerr<<endl;
  // rep(v,N){
  //   cerr<<format("v={}: \n",v);
  //   for(auto i:G[v])cerr<<format("{},{}/",i.first,i.second);
  //   cerr<<endl;
  // }
  atcoder::segtree<pair<int,pii>, seg_op,seg_e> seg(N*2-1);
  rep(i,N*2-1){
    seg.set(i,make_pair(depth[vord[i]],pii{i,i}));
  }

  int Q;
  cin>>Q;
  rep(Q){
    int L,R;
    cin>>L>>R;
    L=toNode[L],R=toNode[R];
    // cerr<<format("L={},R={}\n",L,R);
    if(vout[L]>vin[R])swap(L,R);
    auto [lcadep,lcaidx]=seg.prod(vin[L],vout[R]);
    auto [lcaidxl,lcaidxr]=lcaidx;
    int lca=vord[lcaidxl];
    int ans=dist[L]+dist[R]-dist[lca]*2;
    // cerr<<format("LCA={},l={},r={}\n",lca,lcaidxl,lcaidxr);
    if(lca!=L&&lca!=R){
      int pl=vord[seg.prod(vin[L],lcaidxl).second.first];
      int pr=vord[seg.prod(lcaidxr+1,vout[R]).second.first];
      // cerr<<format("pl={},pr={}\n",pl,pr);
      chmin(ans,dist[L]-dist[pl]+dist[R]-dist[pr]+abs(cIdx[lca][pl]-cIdx[lca][pr]));
    }
    cout<<ans<<'\n';
  }

}