jag_regional_2021_F_riantkb.cpp

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const long long LM = 1LL << 60;

class sqrt_decomp {
  class bucket {
    int l, r, n;
    int flipped;
    int sumall;
    vector<int> v, freq, freq_cumsum, freq_cnt_cumsum, freq_oddcnt_cumsum;

    void construct() {
      if (flipped) {
        for (int i = 0; i < n; ++i) {
          v[i] = -v[i];
        }
        flipped = 0;
      }
      sumall = 0;
      fill(freq.begin(), freq.end(), 0);
      for (auto& i : v) {
        sumall += i;
        ++freq[n + sumall];
      }
      freq_cumsum[0] = 0;
      freq_cnt_cumsum[0] = 0;
      freq_oddcnt_cumsum[0] = 0;
      for (int i = 0; i < (int)freq.size(); ++i) {
        freq_cumsum[i + 1] = freq_cumsum[i] + freq[i] * (i - n);
        freq_cnt_cumsum[i + 1] = freq_cnt_cumsum[i] + freq[i];
        freq_oddcnt_cumsum[i + 1] = freq_oddcnt_cumsum[i] + ((i - n) % 2 != 0 ? freq[i] : 0);
      }
    }

    void update_partial(int l, int r) {
      for (int i = l; i < r; ++i) {
        v[i] = -v[i];
      }
      construct();
    }

    void update_all() {
      flipped = !flipped;
    }

    long long calc_partial(int l, int r, int& depth) {
      long long res = 0;
      for (int i = l; i < r; ++i) {
        if (flipped) {
          depth -= v[i];
        }
        else {
          depth += v[i];
        }
        res += max(0, (1 - depth) / 2);
      }
      return res;
    }

    void calc_depth_partial(int l, int r, int& depth) {
      for (int i = l; i < r; ++i) {
        if (flipped) {
          depth -= v[i];
        }
        else {
          depth += v[i];
        }
      }
    }

    long long calc_all(int& depth) {
      long long res;
      if (flipped) {
        int k = clamp(depth + n, 0, n * 2 + 1);
        if (depth % 2 == 0) {
          res = (freq_cumsum[n * 2 + 1] - freq_cumsum[k]) - depth * (long long)(n - freq_cnt_cumsum[k]) + (freq_oddcnt_cumsum[n * 2 + 1] - freq_oddcnt_cumsum[k]);
        }
        else {
          res = (freq_cumsum[n * 2 + 1] - freq_cumsum[k]) - depth * (long long)(n - freq_cnt_cumsum[k]) + ((n - freq_cnt_cumsum[k]) - (freq_oddcnt_cumsum[n * 2 + 1] - freq_oddcnt_cumsum[k]));
        }
        depth -= sumall;
      }
      else {
        int k = clamp(-depth + n, 0, n * 2 + 1);
        if (depth % 2 == 0) {
          res = -freq_cumsum[k] - depth * (long long)freq_cnt_cumsum[k] + freq_oddcnt_cumsum[k];
        }
        else {
          res = -freq_cumsum[k] - depth * (long long)freq_cnt_cumsum[k] + (freq_cnt_cumsum[k] - freq_oddcnt_cumsum[k]);
        }
        depth += sumall;
      }
      assert(res % 2 == 0 && res >= 0);
      res /= 2;
      return res;
    }

    void calc_depth_all(int& depth) {
      if (flipped) {
        depth -= sumall;
      }
      else {
        depth += sumall;
      }
    }

  public:
    bucket(const vector<int>& a, int l, int r) : l(l), r(r), n(r - l), flipped(0) {
      v = vector<int>(n);
      for (int i = 0; i < n; ++i) {
        v[i] = a[i + l];
      }
      freq = vector<int>(n * 2 + 1);
      freq_cumsum = vector<int>(n * 2 + 2);
      freq_cnt_cumsum = vector<int>(n * 2 + 2);
      freq_oddcnt_cumsum = vector<int>(n * 2 + 2);
      construct();
    }

    void update(int s, int t) {
      if (r <= s || t <= l) {
        return;
      } else if (s <= l && r <= t) {
        update_all();
      } else {
        update_partial(max(s, l) - l, min(t, r) - l);
      }
    }

    long long calc(int s, int t, int& depth) {
      if (r <= s || t <= l) {
        return 0;
      } else if (s <= l && r <= t) {
        return calc_all(depth);
      } else {
        return calc_partial(max(s, l) - l, min(t, r) - l, depth);
      }
    }

    void calc_depth(int s, int t, int& depth) {
      if (r <= s || t <= l) {
        return;
      } else if (s <= l && r <= t) {
        calc_depth_all(depth);
      } else {
        calc_depth_partial(max(s, l) - l, min(t, r) - l, depth);
      }
    }
  };

  vector<bucket> v;

public:
  sqrt_decomp(const vector<int>& a, int bucket_size) {
    v = vector<bucket>();
    for (int i = 0; i < (int)a.size(); i += bucket_size) {
      v.emplace_back(a, i, min(i + bucket_size, (int)a.size()));
    }
  }

  void update(int l, int r) {
    for (auto& i : v) {
      i.update(l, r);
    }
  }

  long long calc(int l, int r) {
    int whole_depth = 0;
    for (auto& i : v) {
      i.calc_depth(l, r, whole_depth);
    }
    long long res = 0;
    int depth = 0;
    if (whole_depth > 0) {
      res += whole_depth + (1 + whole_depth / 2) * (long long)((whole_depth + 1) / 2);
      depth -= whole_depth;
    }
    for (auto& i : v) {
      res += i.calc(l, r, depth);
    }
    if (whole_depth < 0) {
      res += -whole_depth + (1 + (-whole_depth - 1) / 2) * (long long)((-whole_depth) / 2);
      depth -= whole_depth;
    }
    assert(depth == 0);
    return res;
  }
};


int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n, q;
  string s;
  cin >> n >> q >> s;
  vector<int> v(n);
  for (int i = 0; i < n; ++i) {
    v[i] = s[i] == '(' ? 1 : -1;
  }
  sqrt_decomp sqd(v, 350);
  for (int _ = 0; _ < q; ++_) {
    int t, l, r;
    cin >> t >> l >> r;
    --l;
    if (t == 1) {
      sqd.update(l, r);
    }
    else {
      cout << sqd.calc(l, r) << '\n';
    }
  }
  return 0;
}