#1180253 (C++23(gcc16)) No.3652 Range Bracket Sequence

• 問題: No.3652 Range Bracket Sequence
• ユーザー: yurina256
• 提出日時: 2026-08-29 09:06:36
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 316 ms / 2,000 ms
• コード長: 5,192 bytes
• コンパイル時間: 6,932 ms
• コンパイル使用メモリ: 396,976 KB
• 実行使用メモリ: 26,496 KB
• 最終ジャッジ日時: 2026-08-29 09:07:00
• 合計ジャッジ時間: 18,892 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 57

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using namespace atcoder;
using mint = modint;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define rrep1(i, n) for (int i = (int)(n) - 1; i >= 1; i--)
#define ll long long
#define double long double
#define ull unsigned long long
#define ALL(v) (v).begin(), (v).end()
#define NP next_permutation
#define PLL pair<long long, long long>
#define VL vector<long long>
#define VVL vector<vector<long long>>
#define VVVL vector<vector<vector<long long>>>
#define VPLL vector<pair<long long, long long>>
#define STL set<long long>
#define MPLL map<long long, long long>
#define SP fixed << setprecision(12)
#define hashmap unordered_set
#define popcount __builtin_popcountll

constexpr ll inf = 4001001001001001001ll;
constexpr ll mod = 100003;  ///* 1000000007; //*/ 998244353;
constexpr double pi = 3.141592653589793;
constexpr double eps = 0.00000000001;
vector<ll> d8x = {1, 1, 0, -1, -1, -1, 0, 1};
vector<ll> d8y = {0, 1, 1, 1, 0, -1, -1, -1};
vector<ll> d4x = {1, 0, -1, 0};
vector<ll> d4y = {0, 1, 0, -1};
// 小数出力
// cout << setprecision(12);
// struct
typedef tree<
    int,
    null_type,
    less<int>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;
struct Ruiseki {
  vector<ll> v;
  Ruiseki(vector<ll>& vec) {
    ll n = vec.size();
    v.resize(n + 1);
    rep(i, n) v[i + 1] = v[i] + vec[i];
  }
  ll get(ll l, ll r) {  // 開区間になりました
    return v[r] - v[l];
  }
};
// max
template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); }
// min
template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); }
// join
template <typename T>
string join(vector<T>& vec, const string& sp = " ") {
  int si = vec.size();
  if (si == 0) {
    return "";
  } else {
    stringstream ss;
    rep(i, si - 1) {
      ss << vec[i] << sp;
    }
    ss << vec[si - 1];
    return ss.str();
  }
}
// print
template <typename T>
void pr_single(const T& x) {
  if constexpr (requires { x.val(); }) cout << x.val();
  else if constexpr (requires { typename T::value_type; } && !requires { x.substr(0); }) {
    using elem_type = typename T::value_type;
    constexpr bool is_container_of_container =
        requires { typename elem_type::value_type; } &&
        !requires(elem_type e) { e.substr(0); };
    for (int i = 0; i < (int)x.size(); i++) {
      pr_single(x[i]);
      if (i != (int)x.size() - 1) {
        if constexpr (is_container_of_container) {
          cout << "\n";
        } else {
          cout << " ";
        }
      }
    }
  } else if constexpr (requires { x.first; x.second; }) {
    pr_single(x.first);
    cout << " ";
    pr_single(x.second);
  } else if constexpr (requires { cout << x; }) {
    cout << x;
  }
}
void pr() { cout << endl; }
template <typename Head, typename... Tail>
void pr(const Head& head, const Tail&... tail) {
  pr_single(head);
  if constexpr (sizeof...(tail) > 0) {
    cout << " ";
    pr(tail...);
  } else
    cout << endl;
}
// Yes
string Yes(bool x) {
  if (x) return "Yes\n";
  return "No\n";
}
string YES(bool x) {
  if (x) return "YES\n";
  return "NO\n";
}
ll Digit(ll n) {
  ll ans = 0;
  while (n > 0) {
    n /= 10;
    ans++;
  }
  return ans;
}
bool in_range(int l, int x, int r) {  // 閉区間
  return ((l <= x) && (x <= r)) || ((r <= x) && (x <= l));
}
int div_ceil(int x, int y) {
  return (x + y - 1) / y;
}
void yakubun(ll& a, ll& b) {
  if (a < 0) {
    a = -a;
    b = -b;
  }
  if (a == 0) {
    b = 1;
    return;
  }
  if (b == 0) {
    a = 1;
    return;
  }
  ll g = gcd(abs(a), abs(b));
  a /= g;
  b /= g;
  // pr(a, b);
}
void swap(pair<ll, ll>& p) {
  auto [a, b] = p;
  p = {b, a};
}
ll _sqrt(ll x) {
  ll a = sqrt(x);
  while ((a + 1) * (a + 1) <= x) a++;
  while (a * a > x) a--;
  return a;
}
ll _pow(ll x, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
ll bs(ll l, ll r, function<bool(ll)> f) {  // l-> false, r->true
  while (r - l > 1) {
    ll mid = l + (r - l) / 2;
    if (f(mid)) r = mid;
    else
      l = mid;
  }
  return r;
}
struct S {
  ll len, l, r, sum;
};
S op(S a, S b) {
  ll k = min(a.r, b.l);
  if (a.r > k) b.r += a.r - k;
  if (b.l > k) a.l += b.l - k;
  return {a.len + b.len, a.l, b.r, a.sum + b.sum + k};
}
S e() {
  return {0, 0, 0, 0};
}
signed main() {
  ll n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  vector<S> seg_base(n, {1, 0, 0, 0});
  rep(i, n) {
    char c = s[i];
    if (c == ')') seg_base[i].l = 1;
    else
      seg_base[i].r = 1;
  }
  atcoder::segtree<S, op, e> seg(seg_base);
  rep(Q, q) {
    ll type;
    cin >> type;
    if (type == 1) {
      ll x, t;
      cin >> x >> t;
      S a = {1, 0, 1, 0};
      S b = {1, 1, 0, 0};
      seg.set(x - 1, ((t == 1) ? a : b));
    } else {
      ll l, r;
      cin >> l >> r;
      l--;
      pr(seg.prod(l, r).sum * 2);
    }
  }
}