/* このコード、と~おれ! Be accepted! ∧_∧  (。・ω・。)つ━☆・*。 ⊂   ノ    ・゜+.  しーJ   °。+ *´¨)          .· ´¸.·*´¨) ¸.·*¨)           (¸.·´ (¸.·'* ☆ */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#pragma GCC target("arch=skylake-avx512") #pragma GCC target("avx2") //#pragma GCC optimize("O3") #pragma GCC optimize("Ofast") //#pragma GCC target("sse4") #pragma GCC optimize("unroll-loops") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #define repeat(i, n, m) for(int i = n; i < (m); ++i) #define rep(i, n) for(int i = 0; i < (n); ++i) #define printynl(a) printf(a ? "yes\n" : "no\n") #define printyn(a) printf(a ? "Yes\n" : "No\n") #define printYN(a) printf(a ? "YES\n" : "NO\n") #define printim(a) printf(a ? "possible\n" : "imposible\n") #define printdb(a) printf("%.50lf\n", a) #define printLdb(a) printf("%.50Lf\n", a) #define printdbd(a) printf("%.16lf\n", a) #define prints(s) printf("%s\n", s.c_str()) #define all(x) (x).begin(), (x).end() #define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI) #define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L) #define Please return #define AC 0 #define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) using ll = long long; using ull = unsigned long long; constexpr int INF = 1073741823; constexpr int MINF = -1073741823; constexpr ll LINF = ll(4661686018427387903); constexpr ll MOD = 1e9 + 7; constexpr ll mod = 998244353; constexpr long double eps = 1e-14; const long double PI = acosl(-1.0L); using namespace std; void scans(string& str) { char c; str = ""; scanf("%c", &c); if (c == '\n')scanf("%c", &c); while (c != '\n' && c != -1 && c != ' ') { str += c; scanf("%c", &c); } } void scanc(char& str) { char c; scanf("%c", &c); if (c == -1)return; while (c == '\n') { scanf("%c", &c); } str = c; } double acot(double x) { return PI / 2 - atan(x); } ll LSB(ll n) { return (n & (-n)); } template inline T chmin(T& a, const T& b) { if (a > b)a = b; return a; } template inline T chmax(T& a, const T& b) { if (a < b)a = b; return a; } //cpp_int #if __has_include() #include #include using namespace boost::multiprecision; #else using cpp_int = ll; #endif //atcoder library #if __has_include() #include //using namespace atcoder; #endif /* random_device seed_gen; mt19937 engine(seed_gen()); uniform_int_distribution dist(1, 100); */ /*----------------------------------------------------------------------------------*/ /* * @title Mo's Algorithm * @docs kyopro/docs/mo.md */ template struct mo { int sqn, q, l, r, p; T ret; vector> query; vector ans; mo(const int& n, const int& q) : sqn((int)std::sqrt(n)), q(q), l(0), r(0), p(0), ret(T({ 0, 0 })), query(q), ans(q) {} inline void insert(const int& l, const int& r) { query[p] = { l, r, p }; ++p; } inline void read(const bool& oneindexed) { for (auto& [left, right, idx] : query) { scanf("%d%d", &left, &right); if (oneindexed)--left; idx = p++; } } void build() { sort(all(query), [&](const tuple& a, const tuple& b) { if (get<0>(a) / sqn != get<0>(b) / sqn)return get<0>(a) < get<0>(b); return get<1>(a) < get<1>(b); }); } void run(const ADD_LEFT& add_left, const ADD_RIGHT& add_right, const DEL_LEFT& del_left, const DEL_RIGHT& del_right, const REM& rem) { for (const auto& [ql, qr, qo] : query) { while (l > ql)add_left(--l, ret); while (r < qr)add_right(r++, ret); while (l < ql)del_left(l++, ret); while (r > qr)del_right(--r, ret); rem(qo, ans, ret); } } void run(const ADD_LEFT& add, const DEL_LEFT& del, const REM& rem) { run(add, add, del, del, rem); } T operator [](const int& idx) { return ans[idx]; } void allrun(const bool& oneindexed, const ADD_LEFT& add_left, const ADD_RIGHT& add_right, const DEL_LEFT& del_left, const DEL_RIGHT& del_right, const REM& rem) { read(oneindexed); build(); run(add_left, add_right, del_left, del_right, rem); } void allrun(const bool& oneindexed, const ADD_LEFT& add, const DEL_LEFT& del, const REM& rem) { allrun(oneindexed, add, add, del, del, rem, rem); } }; struct Node { Node* left, * right; ll v; Node() : left(nullptr), right(nullptr), v(0) {} }; // Dynamic Segment Tree class SegmentTree { Node* root; int n, n0; int query(int a, int b, Node* n, int l, int r) { if (a <= l && r <= b) { return n->v; } if (r <= a || b <= l) { return 0; } int lv = n->left ? query(a, b, n->left, l, (l + r) >> 1) : 0; int rv = n->right ? query(a, b, n->right, (l + r) >> 1, r) : 0; return (lv + rv) % MOD; } public: SegmentTree(int n) : n(n) { n0 = 1; while (n0 < n) n0 <<= 1; root = new Node(); } ~SegmentTree() { delete root; root = nullptr; } void update(int k, ll x) { Node* n = root; int l = 0, r = n0; n->v = (n->v + x); while (r - l > 1) { int m = (l + r) >> 1; if (k < m) { if (!n->left) n->left = new Node(); n = n->left; r = m; } else { if (!n->right) n->right = new Node(); n = n->right; l = m; } n->v = (n->v + x); } } int query(int a, int b) { return query(a, b, root, 0, n0); } int lquery(int b) { return query(0, b, root, 0, n0); } int rquery(int a) { return query(a, n0, root, 0, n0); } }; //from: https://tjkendev.github.io/procon-library/cpp/range_query/dynamic_segment_tree.html int main() { int n, m, q; scanf("%d%d%d", &n, &m, &q); vector> a(n); SegmentTree *seg[200000]; rep(i, m)seg[i] = new SegmentTree(n); rep(i, n) { scanf("%d%*c", &a[i].first); --a[i].first; scans(a[i].second); if (a[i].second == "WA") seg[a[i].first]->update(i, 1); } vector wa(m); vector> ac(m); int right = 0, left = 0; auto add_l = [&](const int& idx, pair& ret) { if (a[idx].second == "AC") { if (ac[a[idx].first].empty())++ret.first; ac[a[idx].first].insert(idx); ret.second -= wa[a[idx].first]; wa[a[idx].first] = 0; } else { if (not ac[a[idx].first].empty()) { ++wa[a[idx].first]; ++ret.second; } } left = idx; }; auto add_r = [&](const int& idx, pair& ret) { if (a[idx].second == "AC") { if (ac[a[idx].first].empty()) { ++ret.first; ret.second += seg[a[idx].first]->query(left, idx); wa[a[idx].first] += seg[a[idx].first]->query(left, idx); } ac[a[idx].first].insert(idx); } right = idx + 1; }; auto del_l = [&](const int& idx, pair& ret) { if (a[idx].second == "AC") { ac[a[idx].first].erase(idx); if (ac[a[idx].first].empty()) { --ret.first; ret.second -= wa[a[idx].first]; wa[a[idx].first] = 0; } else { wa[a[idx].first] += seg[a[idx].first]->query(idx, ac[a[idx].first].empty() ? right : *ac[a[idx].first].begin()); ret.second += seg[a[idx].first]->query(idx, ac[a[idx].first].empty() ? right : *ac[a[idx].first].begin()); } } else { if (not ac[a[idx].first].empty()) { --wa[a[idx].first]; --ret.second; } } left = idx + 1; }; auto del_r = [&](const int& idx, pair& ret) { if (a[idx].second == "AC") { ac[a[idx].first].erase(idx); if (ac[a[idx].first].empty()) { --ret.first; ret.second -= wa[a[idx].first]; wa[a[idx].first] = 0; } } right = idx; }; vector> ans(q); auto rem = [](const int& idx, vector>& ans, const pair& ret) { ans[idx] = ret; }; mo> mo(n, q); mo.allrun(true, add_l, add_r, del_l, del_r, rem); rep(i, q)printf("%d %d\n", mo[i].first, mo[i].second); Please AC; }