#include #include #include #include #include using namespace std; using i64 = long long; #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) #define all(x) x.begin(),x.end() #define STRINGIFY(n) #n #define TOSTRING(n) STRINGIFY(n) #define PREFIX "#" TOSTRING(__LINE__) "| " #define debug(x) \ { \ std::cout << PREFIX << #x << " = " << x << std::endl; \ } std::ostream& output_indent(std::ostream& os, int ind) { for(int i = 0; i < ind; i++) os << " "; return os; } template std::ostream& operator<<(std::ostream& os, const std::pair& p); template std::ostream& operator<<(std::ostream& os, const std::vector& v); template std::ostream& operator<<(std::ostream& os, const std::pair& p) { return (os << "(" << p.first << ", " << p.second << ")"); } template std::ostream& operator<<(std::ostream& os, const std::vector& v) { os << "["; for(int i = 0;i < v.size();i++) os << v[i] << ", "; return (os << "]"); } template static inline std::vector ndvec(size_t&& n, T val) { return std::vector(n, std::forward(val)); } template static inline auto ndvec(size_t&& n, Tail&&... tail) { return std::vector(tail)...))>(n, ndvec(std::forward(tail)...)); } struct Mo { vector left, right, order; vector v; const i64 width; i64 nl, nr, ptr; vector P; vector S; vector> was; i64 AC = 0; i64 WA = 0; Mo(i64 n, i64 w) : v(n), width(w), nl(0), nr(0), ptr(0) {} void add_query(i64 l, i64 r) { left.push_back(l); right.push_back(r); } void build() { order.resize(left.size()); for(i64 i = 0;i < left.size();i++) order[i] = i; sort(begin(order), end(order), [&](i64 a, i64 b) { if(left[a] / width != left[b] / width) return left[a] < left[b]; else return right[a] < right[b]; }); } i64 process() { if(ptr == order.size()) return -1; const auto id = order[ptr]; while(nl > left[id]) { // left add --nl; int p = P[nl]; if(S[nl] == 0) { was[p].front()++; if(was[p].size() > 1) WA++; } else { if(was[p].size() > 1) { WA -= was[p].front(); } was[p].push_front(0); if(was[p].size() == 2) AC++; } } while(nr < right[id]) { int p = P[nr]; if(S[nr] == 0) { was[p].back()++; } else { if(was[p].size() == 1) { AC++; WA += was[p].back(); } was[p].push_back(0); } nr++; } while(nl < left[id]) { int p = P[nl]; if(S[nl] == 0) { was[p].front()--; if(was[p].size() > 1) WA--; } else { if(was[p].size() == 2) AC--; was[p].pop_front(); if(was[p].size() > 1) { WA += was[p].front(); } } nl++; } while(nr > right[id]) { nr--; int p = P[nr]; if(S[nr] == 0) { was[p].back()--; } else { if(was[p].size() == 2) { AC--; WA -= was[p].back(); } was[p].pop_back(); } } return order[ptr++]; } }; int main() { int N, M, Q; cin >> N >> M >> Q; Mo mo(N, sqrt(3) * N / (sqrt(2 * Q))); mo.P.resize(N); mo.S.resize(N); mo.was.resize(M, std::deque { 0 }); for(int i = 0; i < N; i++) { int p; string s; cin >> p >> s; mo.P[i] = p - 1; mo.S[i] = s == "AC" ? 1 : 0; } for(int i = 0; i < Q; i++) { int l, r; cin >> l >> r; mo.add_query(l - 1, r); } mo.build(); std::vector A(Q), B(Q); for(int i = 0; i < Q; i++) { int q = mo.process(); A[q] = mo.AC; B[q] = mo.WA; } for(int i = 0; i < Q; i++) { cout << A[i] << " " << B[i] << endl; } }