まず、以下のように問題の設定を変更します。

• 初期状態において、蟻 \(1\) は旗を持っている。
• 蟻同士は衝突しない（同じ座標に到達した場合は方向転換することなくすれ違う）が、旗を持った蟻が他の蟻とすれ違った際にはその蟻に旗を渡す。
• 蟻 \(1\) と他の蟻の衝突時刻ではなく、旗を持った蟻と他の蟻がすれ違う（旗の受け渡しが起こる）時刻を考え、これを早い順に \(t_1,t_2,\dots\) とする。

正当性は、蟻の（位置、向き）の組の集合が元の問題と常に一致すること、および旗を持った蟻の（位置、向き）が元の問題における蟻 \(1\) のそれと常に一致することから従います。

ここで、初期状態において

• 蟻 \(1\) より右にいて、進行方向が右である蟻
• 蟻 \(1\) より左にいて、進行方向が左である蟻

は今後旗を持つ可能性がなく問題に関係がないので、そのような蟻は最初からいないものとしてしまいます（＊）。

一般性を失わず、蟻 \(1\) が初期状態において左を向いていると仮定します。初期状態において、蟻 \(1\) より左にいる蟻の番号を座標の降順に並べてできる列を \(l_1,l_2,\dots,l_L\)、蟻 \(1\) より右にいる蟻の番号を座標の昇順に並べてできる列を \(r_1,r_2,\dots,r_R\) とします。上述の仮定（＊）より、すべての蟻 \(l_i\) は初期状態で右を、すべての蟻 \(r_i\) は初期状態で左を向いていることに注意してください。

このとき、旗を持つ蟻の番号は \(1\rightarrow l_1 \rightarrow r_1 \rightarrow l_2 \rightarrow r_2 \rightarrow \dots\) と移り変わっていきます。旗が蟻 \(x\) から蟻 \(y\) に受け渡される時刻は、単に初期状態から蟻 \(x,y\) が移動を始めた際に \(2\) 匹が同じ座標に到達する時刻なので、旗の受け渡しが起こる時刻は早い順に \(\frac{X_1-X_{l_1}}{2},\frac{X_{r_1}-X_{l_1}}{2},\frac{X_{r_1}-X_{l_2}}{2},\frac{X_{r_2}-X_{l_2}}{2},\dots\) となります。

それではクエリの処理について考えます。\(f(x)=t_1+t_2+\dots+t_x\) として、与えられた \(x\) についての \(f(x)\) が高速に求められれば \(2\) 種類目のクエリは処理できます（クエリ 2 l r への答えは \(f(r)-f(l-1)\) で得られます）。\(x\) が偶数の場合、

\[\begin{aligned} f(x) &=\frac{1}{2}((X_1-X_{l_1})+(X_{r_1}-X_{l_1})+(X_{r_1}-X_{l_2})+(X_{r_2}-X_{l_2})+\dots+(X_{r_{x/2}}-X_{l_{x/2}})) \\ &= \displaystyle\sum_{i=1}^{x/2} X_{r_i} -\sum_{i=1}^{x/2} X_{l_i}+\frac{1}{2}(X_1-X_{r_{x/2}}) \end{aligned}\]

であり、\(x\) が奇数のときも似たような形の式で表されます。よって、結局以下のような問題が解ければよいです。

• 整数の集合 \(X\) が与えられる。以下のいずれかの形式のクエリが合計で \(Q\) 回与えられるので、順に処理せよ。
  • 1 x: \(X\) に \(x\) を追加する。
  • 2 k: \(X\) の要素のうち小さい方から \(k\) 個の総和を出力する。

これは座標圧縮 + segment tree によって解くことができます。

よって、本問題を \(O((N+Q)\log(N+Q))\) で解くことができました。

実装例 (C++) :

#include <bits/stdc++.h>
#include <atcoder/segtree>

using namespace std;
using namespace atcoder;

using ll = long long;

// {個数、座標の和}
using S = pair<int, ll>;

S op(S a, S b) { return {a.first + b.first, a.second + b.second}; }

S e() { return {0, 0}; }

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> x(n), d(n); // 0: left  1: right
    for (int i = 0; i < n; i++) {
        char c;
        cin >> x[i] >> c;
        d[i] = (c == 'R');
    }
    vector<int> t(q), l(q), r(q);
    for (int i = 0; i < q; i++) {
        cin >> t[i];
        if (t[i] == 1) {
            x.push_back(0);
            char c;
            cin >> x.back() >> c;
            d.push_back(c == 'R');
        } else {
            cin >> l[i] >> r[i];
        }
    }
    if (d[0]) {
        for (int &i: x) i *= -1;
        for (int &i: d) i ^= 1;
    }
    auto ori_x = x;
    sort(ori_x.begin(), ori_x.end());
    for (int &i: x) i = lower_bound(ori_x.begin(), ori_x.end(), i) - ori_x.begin();
    segtree<S, op, e> st(x.size());
    auto add = [&](int nx, int nd) {
        if ((nx < x[0]) xor !nd) st.set(nx, {1, ori_x[nx]});
    };
    // t_1 + ... + t_k
    auto sum = [&](int k) -> ll {
        if (!k) return 0;
        ll res = 0;
        int lp, rp;
        if (k & 1) {
            lp = st.min_left(x[0], [&](S s) { return s.first < (k + 1) / 2; }) - 1;
            rp = st.max_right(x[0], [&](S s) { return s.first < (k + 1) / 2; });
            res -= ori_x[x[0]];
            res += ori_x[lp];
        } else {
            lp = st.min_left(x[0], [&](S s) { return s.first < k / 2; }) - 1;
            rp = st.max_right(x[0], [&](S s) { return s.first < k / 2 + 1; });
            res -= ori_x[x[0]];
            res -= ori_x[rp];
        }
        res -= st.prod(lp, x[0]).second * 2;
        res += st.prod(x[0], rp + 1).second * 2;
        res /= 2;
        return res;
    };
    int it = 0;
    for (int i = 0; i < n; i++) {
        add(x[it], d[it]);
        it++;
    }
    for (int i = 0; i < q; i++) {
        if (t[i] == 1) {
            add(x[it], d[it]);
            it++;
        } else {
            cout << sum(r[i]) - sum(l[i] - 1) << '\n';
        }
    }
}