#include #ifdef LOCAL #include #else #define debug(...) void(0) #endif struct Mo { Mo(int n) : n(n) {} void add(int l, int r) { assert(l <= r); left.emplace_back(l); right.emplace_back(r); } template void run(const AL& add_left, const AR& add_right, const DL& del_left, const DR del_right, const REM& rem) { int q = left.size(), width = n / std::min(std::max(sqrt(q * 2 / 3), 1), n); std::vector order(q); std::iota(order.begin(), order.end(), 0); std::sort(order.begin(), order.end(), [&](int a, int b) { int ablock = left[a] / width, bblock = left[b] / width; if (ablock != bblock) return ablock < bblock; return (ablock & 1) ? (right[a] > right[b]) : (right[a] < right[b]); }); int l = 0, r = 0; for (auto idx : order) { while (l > left[idx]) add_left(--l); while (r < right[idx]) add_right(r++); while (l < left[idx]) del_left(l++); while (r > right[idx]) del_right(--r); rem(idx); } } template void run(const A& add, const D& del, const REM& rem) { run(add, add, del, del, rem); } private: int n; std::vector left, right; }; template struct BinaryIndexedTree { BinaryIndexedTree() : n(0) {} BinaryIndexedTree(int n) : n(n), data(n) {} void add(int k, T x) { assert(0 <= k && k < n); for (k++; k <= n; k += k & -k) data[k - 1] += x; } T query(int l, int r) const { assert(0 <= l && l <= r && r <= n); return sum(r) - sum(l); } T operator[](int i) const { return query(i, i + 1); } int lower_bound(T x) const { if (x <= 0) return 0; int cur = 0, k = 1; while (k < n) k <<= 1; for (; k > 0; k >>= 1) { if (cur + k <= n && data[cur + k - 1] < x) { x -= data[cur + k - 1]; cur += k; } } return cur; } int upper_bound(T x) const { return lower_bound(x + 1); } private: int n; std::vector data; T sum(int r) const { T res = 0; for (; r > 0; r -= r & -r) res += data[r - 1]; return res; } }; using namespace std; typedef long long ll; #define all(x) begin(x), end(x) constexpr int INF = (1 << 30) - 1; constexpr long long IINF = (1LL << 60) - 1; constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; template istream& operator>>(istream& is, vector& v) { for (auto& x : v) is >> x; return is; } template ostream& operator<<(ostream& os, const vector& v) { auto sep = ""; for (const auto& x : v) os << exchange(sep, " ") << x; return os; } template bool chmin(T& x, U&& y) { return y < x and (x = forward(y), true); } template bool chmax(T& x, U&& y) { return x < y and (x = forward(y), true); } template void mkuni(vector& v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } template int lwb(const vector& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, Q; cin >> N >> M >> Q; vector P(N), S(N); for (int i = 0; i < N; i++) { string tmp; cin >> P[i] >> tmp; P[i]--; S[i] = (tmp == "AC"); } Mo mo(N); for (int i = 0; i < Q; i++) { int L, R; cin >> L >> R; mo.add(--L, R); } vector> cand(M); for (int i = 0; i < N; i++) cand[P[i]].emplace_back(i); for (int i = 0; i < N; i++) mkuni(cand[i]); vector> ac(M), wa(M); for (int i = 0; i < M; i++) { ac[i] = BinaryIndexedTree(cand[i].size()); wa[i] = BinaryIndexedTree(cand[i].size()); } int correct = 0, penalty = 0; auto calc = [&](int idx) { if (ac[idx].query(0, cand[idx].size()) == 0) return 0; int x = ac[idx].lower_bound(1); return wa[idx].query(0, x); }; auto add = [&](int idx) { int x = P[idx]; { correct -= (ac[x].query(0, cand[x].size()) > 0); penalty -= calc(x); } if (S[idx] == 0) wa[x].add(lwb(cand[x], idx), 1); else ac[x].add(lwb(cand[x], idx), 1); { correct += (ac[x].query(0, cand[x].size()) > 0); penalty += calc(x); } }; auto del = [&](int idx) { int x = P[idx]; { correct -= (ac[x].query(0, cand[x].size()) > 0); penalty -= calc(x); } if (S[idx] == 0) wa[x].add(lwb(cand[x], idx), -1); else ac[x].add(lwb(cand[x], idx), -1); { correct += (ac[x].query(0, cand[x].size()) > 0); penalty += calc(x); } }; vector ans1(Q), ans2(Q); auto rem = [&](int idx) { ans1[idx] = correct; ans2[idx] = penalty; }; mo.run(add, del, rem); for (int i = 0; i < Q; i++) cout << ans1[i] << ' ' << ans2[i] << '\n'; return 0; }