以下の一方通行な三状態について考察します。

1. 一度も操作を行っていない
2. 操作を行っている区間である
3. すでに操作を実行した

この三状態について、区間内である状態からある状態への遷移にかかるコストの総和の最小値をセグメント木に乗せておくことで管理することができます。単体の区間でコストがかかるのはTの場合は状態2から状態2の場合のみ。Aの場合は状態1から状態1と状態3から状態3のみ。それ以外の場合は常にコスト \(0\) で遷移することができます。

計算量は\(O((N+Q)\log{N})\)です。

#include <vector>
#include <array>
#include <iostream>
#include <atcoder/segtree>

using namespace std;
using ll = long long;

using val = array<array<ll, 3>, 3>;

val op(val a, val b) {
  val res;
  for (int i = 0; i < 3; i++)
    for (int j = i; j < 3; j++)
      res[i][j] = 1e18;
  for (int i = 0; i < 3; i++)
    for (int j = i; j < 3; j++)
      for (int k = j; k < 3; k++) 
        res[i][k] = min(res[i][k], a[i][j] + b[j][k]);
  return res;
}
array<ll, 3> z = { 0,0,0 };
val e() {
  return { z,z,z };
}


int main() {
  ll n, q;
  cin >> n >> q;
  atcoder::segtree<val, op, e> st(n);
  for (int i = 0; i < n; i++) {
    char s; ll p;
    cin >> s >> p;
    val add = e();
    if (s == 'A')
      add[0][0] = add[2][2] = p;
    else
      add[1][1] = p;
    st.set(i, add);
  }
  while (q--) {
    ll l, r;
    cin >> l >> r;
    auto res = st.prod(l - 1, r);
    cout << min({ res[0][0],res[0][1],res[0][2] }) << "\n";
  }
  return 0;
}