#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vll; typedef vector vvll; typedef vector vull; typedef vector vvull; typedef vector vstring; typedef complex cd; typedef complex ci; typedef complex cll; string toYN(bool b) { return b ? "Yes" : "No"; } // https://ei1333.github.io/luzhiled/snippets/other/random-number-generator.html struct RandomNumberGenerator { mt19937 mt; RandomNumberGenerator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {} int operator()(int a, int b) { // [a, b) uniform_int_distribution dist(a, b - 1); return dist(mt); } int operator()(int b) { // [0, b) return (*this)(0, b); } }; // loop macro #define REP(i, n) for (int i = 0; i < (int)(n); i++) // read helper template inline void read(int n, std::vector &array) { array = std::vector(n); REP(i, n) { cin >> array[i]; } } template inline void read(int n, int m, std::vector> &matrix) { matrix = std::vector>(n, std::vector(m)); REP(i, n) { REP(j, m) { cin >> matrix[i][j]; } } } // write helper template inline void write(std::vector array) { for (const T &t : array) { cout << t << endl; } } template inline void writeOneLine(std::vector array) { bool first = true; for (const T &t : array) { if (!first) { cout << " "; } cout << t; first = false; } cout << endl; } // vector helper // test by iterator_macro_test.cpp template inline typename vector::const_iterator moreThan( const std::vector &sortedVector, const T &key) { return upper_bound(sortedVector.begin(), sortedVector.end(), key); } template inline typename vector::const_iterator moreThanEq( const std::vector &sortedVector, const T &key) { return lower_bound(sortedVector.begin(), sortedVector.end(), key); } template inline typename vector::const_iterator lessThan( const std::vector &sortedVector, const T &key) { typename vector::const_iterator it = lower_bound(sortedVector.begin(), sortedVector.end(), key); return it == sortedVector.begin() ? sortedVector.end() : --it; } template inline typename vector::const_iterator lessThanEq( const std::vector &sortedVector, const T &key) { typename vector::const_iterator it = upper_bound(sortedVector.begin(), sortedVector.end(), key); return it == sortedVector.begin() ? sortedVector.end() : --it; } // set helper // test by iterator_macro_test.cpp template inline typename set::const_iterator moreThan(const set &container, const T &key) { return container.upper_bound(key); } template inline typename set::const_iterator moreThanEq(const set &container, const T &key) { return container.lower_bound(key); } template inline typename set::const_iterator lessThan(const set &container, const T &key) { typename set::const_iterator it = container.lower_bound(key); return it == container.begin() ? container.end() : --it; } template inline typename set::const_iterator lessThanEq(const set &container, const T &key) { typename set::const_iterator it = container.upper_bound(key); return it == container.begin() ? container.end() : --it; } // multiset helper template inline typename multiset::const_iterator moreThan( const multiset &container, T key) { return container.upper_bound(key); } template inline typename multiset::const_iterator moreThanEq( const multiset &container, T key) { return container.lower_bound(key); } template inline typename multiset::const_iterator lessThan( const multiset &container, T key) { typename set::const_iterator it = container.lower_bound(key); return it == container.begin() ? container.end() : --it; } template inline typename multiset::const_iterator lessThanEq( const multiset &container, T key) { typename set::const_iterator it = container.upper_bound(key); return it == container.begin() ? container.end() : --it; } // map helper // test by iterator_macro_test.cpp template inline typename map::const_iterator moreThan( const map &container, const Key &key) { return container.upper_bound(key); } template inline typename map::const_iterator moreThanEq( const map &container, const Key &key) { return container.lower_bound(key); } template inline typename map::const_iterator lessThan( const map &container, const Key &key) { typename map::const_iterator it = container.lower_bound(key); return it == container.begin() ? container.end() : --it; } template inline typename map::const_iterator lessThanEq( const map &container, const Key &key) { typename map::const_iterator it = container.upper_bound(key); return it == container.begin() ? container.end() : --it; } // https://qiita.com/ganyariya/items/df35d253726269bda436 // // Usage: unordered_map, int, HashPair> mp; struct HashPair { template size_t operator()(const pair &p) const { auto hash1 = hash{}(p.first); auto hash2 = hash{}(p.second); size_t seed = 0; seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2); return seed; } }; // debug macro // https://www.creativ.xyz/dump-cpp-652/ // // test by dump_macro_test.cpp #define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) // vector template istream &operator>>(istream &is, vector &vec) { for (T &x : vec) is >> x; return is; } // pair template ostream &operator<<(ostream &os, const pair &pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // vector template ostream &operator<<(ostream &os, const vector &vec) { os << "{"; for (unsigned int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); } os << "}"; return os; } // deque template ostream &operator<<(ostream &os, const deque &vec) { os << "{"; for (unsigned int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); } os << "}"; return os; } // map template ostream &operator<<(ostream &os, map &map_var) { os << "{"; repi(itr, map_var) { os << *itr; itr++; if (itr != map_var.end()) os << ", "; itr--; } os << "}"; return os; } // set template ostream &operator<<(ostream &os, set &set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } // unordered_map template ostream &operator<<(ostream &os, unordered_map &map_var) { os << "{"; repi(itr, map_var) { os << *itr << ", "; } os << "}"; return os; } // unordered_map with HashFunction template ostream &operator<<(ostream &os, unordered_map &map_var) { os << "{"; repi(itr, map_var) { os << *itr << ", "; } os << "}"; return os; } // unordered_set template ostream &operator<<(ostream &os, unordered_set &set_var) { os << "{"; repi(itr, set_var) { os << *itr << ", "; } os << "}"; return os; } // unordered_set with HashFunction template ostream &operator<<(ostream &os, unordered_set &set_var) { os << "{"; repi(itr, set_var) { os << *itr << ", "; } os << "}"; return os; } // dynamic_modint ostream &operator<<(ostream &os, const modint &modint_value) { os << modint_value.val(); return os; } // static_modint template ostream &operator<<(ostream &os, const static_modint &modint_value) { os << modint_value.val(); return os; } #define DUMPOUT cerr void dump_func() { DUMPOUT << endl; } template void dump_func(Head &&head, Tail &&...tail) { DUMPOUT << head; if (sizeof...(Tail) > 0) { DUMPOUT << ", "; } dump_func(std::move(tail)...); } #ifdef DEBUG_ #define DEB #define dump(...) \ DUMPOUT << " " << string(#__VA_ARGS__) << ": " \ << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl \ << " ", \ dump_func(__VA_ARGS__) // vector> template void dumpVV(const vector> &vec) { DUMPOUT << "{" << endl; for (int i = 0; i < vec.size(); i++) { DUMPOUT << " " << vec[i] << endl; } DUMPOUT << "}" << endl; } template void dumpSegtree(const segtree &segtree, int size) { DUMPOUT << "{"; for (int i = 0; i < size; i++) { if (i > 0) { DUMPOUT << ", "; } DUMPOUT << segtree.get(i); } DUMPOUT << "}" << endl; } template void dumpLazySegtree( lazy_segtree &lazySegtree, int size) { DUMPOUT << "{"; for (int i = 0; i < size; i++) { if (i > 0) { DUMPOUT << ", "; } DUMPOUT << lazySegtree.get(i); } DUMPOUT << "}" << endl; } #else #define DEB if (false) #define dump(...) // vector> template void dumpVV(const vector> &vec) { // Do nothing } template void dumpSegtree(const segtree &segtree, int size) { // Do nothing } template void dumpLazySegtree( lazy_segtree &lazySegtree, int size) { // Do nothing } #endif typedef tuple query; int op(int a, int b) { return a + b; } int e() { return 0; } const int EXIT_EVENT = 0; const int ENTER_EVENT = 1; class Solver { private: const int n; const vstring xs; const vll ls, rs; const int q; const vector qs; map xToIdMapping; map tToIdMapping; lazy_segtree seg; vector> eventMatrix; void insertEvent(const string &name, ll l, ll r) { int id = xToIdMapping[name]; eventMatrix[id][10 * l - 1] = ENTER_EVENT; eventMatrix[id][10 * r + 1] = EXIT_EVENT; int tId1 = tToIdMapping[10 * l - 1]; int tId2 = tToIdMapping[10 * r + 1]; seg.apply(tId1, tId2 + 1, 1); } public: Solver(int n, const vstring &xs, const vll &ls, const vll &rs, int q, const vector &qs) : n(n), xs(xs), ls(ls), rs(rs), q(q), qs(qs) {} vstring solve() { xToIdMapping = map(); for (const auto &x : xs) { if (!xToIdMapping.count(x)) { int nextId = xToIdMapping.size(); xToIdMapping[x] = nextId; } } for (const auto &p : qs) { string x = get<1>(p); if (!xToIdMapping.count(x)) { int nextId = xToIdMapping.size(); xToIdMapping[x] = nextId; } } set tSet; for (ll l : ls) { tSet.insert(10 * l - 1); tSet.insert(10 * l); } for (ll r : rs) { tSet.insert(10 * r); tSet.insert(10 * r + 1); } for (const auto &p : qs) { ll l = get<2>(p); ll r = get<3>(p); tSet.insert(10 * l - 1); tSet.insert(10 * l); tSet.insert(10 * r); tSet.insert(10 * r + 1); } tToIdMapping = map(); for (ll t : tSet) { int nextId = tToIdMapping.size(); tToIdMapping[t] = nextId; } seg = lazy_segtree(tToIdMapping.size()); eventMatrix = vector>(xToIdMapping.size()); for (int i = 0; i < eventMatrix.size(); i++) { eventMatrix[i][0] = EXIT_EVENT; eventMatrix[i][1e11] = ENTER_EVENT; } for (int i = 0; i < n; i++) { insertEvent(xs[i], ls[i], rs[i]); } vector answers; for (int i = 0; i < q; i++) { int qType = get<0>(qs[i]); if (qType == 1) { string x = get<1>(qs[i]); ll t = get<2>(qs[i]); int id = xToIdMapping[x]; auto it = moreThan(eventMatrix[id], 10 * t); answers.push_back(it->second == EXIT_EVENT ? "YES" : "NO"); } else if (qType == 2) { ll t = get<2>(qs[i]); int id = tToIdMapping[10 * t]; answers.push_back(to_string(seg.get(id))); } else if (qType == 3) { string x = get<1>(qs[i]); ll l = get<2>(qs[i]); ll r = get<3>(qs[i]); insertEvent(x, l, r); } } return answers; } }; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); // Implement here, int n; cin >> n; vstring xs(n); vll ls(n), rs(n); for (int i = 0; i < n; i++) { cin >> xs[i] >> ls[i] >> rs[i]; } int q; cin >> q; vector qs; for (int i = 0; i < q; i++) { int type; cin >> type; if (type == 1) { string x; int t; cin >> x >> t; qs.push_back(query(1, x, t, 0)); } else if (type == 2) { int t; cin >> t; qs.push_back(query(2, "", t, 0)); } else if (type == 3) { string x; int l, r; cin >> x >> l >> r; qs.push_back(query(3, x, l, r)); } } write(Solver(n, xs, ls, rs, q, qs).solve()); }