#line 1 "main.cpp" #include #line 2 "template.cpp" #pragma region templates #pragma region std::vector operator template std::vector &operator++(std::vector &v) { for (auto &e : v) { ++e; } return v; } template std::vector operator++(std::vector &v, int) { auto res = v; for (auto &e : v) { ++e; } return res; } template std::vector &operator--(std::vector &v) { for (auto &e : v) { --e; } return v; } template std::vector operator--(std::vector &v, int) { auto res = v; for (auto &e : v) { --e; } return res; } #pragma endregion #pragma region ios namespace scanner { namespace submodule { void read(int &a) { std::cin >> a; } void read(long long &a) { std::cin >> a; } void read(char &a) { std::cin >> a; } void read(double &a) { std::cin >> a; } void read(std::string &a) { std::cin >> a; } template void read(std::pair &p) { read(p.first); read(p.second); } template void read(std::vector &); template void read(std::vector &a) { for (auto &e : a) { read(e); } } template void read(T &a) { std::cin >> a; } } // namespace submodule void scan() {} template void scan(Head &head, Tail &...tail) { submodule::read(head); scan(tail...); } void scanI() {} template void scanI(Head &head, Tail &...tail) { submodule::read(head); --head; scanI(tail...); } } // namespace scanner template std::ostream &operator<<(std::ostream &os, std::pair pa) { os << '{' << pa.first << ", " << pa.second << '}'; return os; } template std::ostream &operator<<(std::ostream &os, std::vector vec) { os << "{"; const int n = (int)vec.size(); for (int i = 0; i < n; i++) { os << vec[i]; os << (i == n - 1 ? "}" : ", "); } return os; } template std::ostream &operator<<(std::ostream &os, std::array arr) { os << "{"; for (int i = 0; i < (int)S; i++) { os << arr[i]; os << (i == S - 1 ? "}" : ", "); } os << "}"; return os; } template std::ostream &operator<<(std::ostream &os, std::map ma) { os << "{"; auto itr = ma.begin(); while (itr != ma.end()) { os << *itr << (itr == --ma.end() ? "}" : ", "); ++itr; } return os; } template std::ostream &operator<<(std::ostream &os, std::set st) { os << "{"; auto itr = st.begin(); while (itr != st.end()) { os << *itr << (itr == --st.end() ? "}" : ", "); ++itr; } return os; } namespace printer { void print() { std::cout << '\n'; } template void print(const Head &head, const Tail &...tail) { std::cout << head; if (sizeof...(tail)) std::cout << ' '; print(tail...); } } // namespace printer namespace dumper { void dumpFunc() { std::cerr << std::endl; } template void dumpFunc(Head &&head, Tail &&...tail) { std::cerr << head; if (sizeof...(Tail) == 0) { std::cerr << ' '; } else { std::cerr << ", "; } dumpFunc(std::move(tail)...); } } // namespace dumper #pragma endregion #pragma region functions template constexpr int si(const T &c) { return static_cast(c.size()); } template constexpr bool afMin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } template constexpr bool afMax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template constexpr T calcSum(const S &container) { return std::accumulate(container.begin(), container.end(), static_cast(0)); } template constexpr auto calcMin(const T &container) { return *std::min_element(container.begin(), container.end()); } template constexpr auto calcMax(const T &container) { return *std::max_element(container.begin(), container.end()); } template constexpr int lwbi(const T &container, const typename T::value_type &value) { return static_cast(std::distance(container.cbegin(), std::lower_bound(container.cbegin(), container.cend(), value))); } template constexpr int upbi(const T &container, const typename T::value_type &value) { return static_cast(std::distance(container.cbegin(), std::upper_bound(container.cbegin(), container.cend(), value))); } template auto makeVec(const int n, const T &value) { return std::vector(n, value); } template auto makeVec(const int n, Args... args) { return std::vector(n, makeVec(args...)); } template T binarySearch(T ok, T ng, const F &f) { while (abs(ok - ng) > 1) { T mid = ok + ng >> 1; (f(mid) ? ok : ng) = mid; } return ok; } template T binarySearchReal(T ok, T ng, const F &f, int iter = 80) { while (iter--) { T mid = (ok + ng) / 2; (f(mid) ? ok : ng) = mid; } return ok; } #pragma endregion #pragma region macros and vars using namespace scanner; using namespace printer; using i64 = long long; template using Vec = std::vector; template using PQ = std::priority_queue; template using RPQ = std::priority_queue, std::greater>; std::mt19937 mtRand(std::random_device{}()); constexpr std::array, 4> dxy4 = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}}; constexpr std::array, 8> dxy8 = { {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}}; #define INT(...) \ int __VA_ARGS__; \ scan(__VA_ARGS__) #define INTI(...) \ int __VA_ARGS__; \ scanI(__VA_ARGS__) #define I64(...) \ i64 __VA_ARGS__; \ scan(__VA_ARGS__) #define I64I(...) \ i64 __VA_ARGS__; \ scanI(__VA_ARGS__) #define STR(...) \ std::string __VA_ARGS__; \ scan(__VA_ARGS__) #define CHR(...) \ char __VA_ARGS__; \ scan(__VA_ARGS__) #define DOUBLE(...) \ double __VA_ARGS__; \ scan(__VA_ARGS__) #define VEC(type, name, n) \ std::vector name(n); \ scan(name) #define VECI(type, name, n) \ std::vector name(n); \ scanI(name) #define VEC2(type, name1, name2, n) \ std::vector name1(n), name2(n); \ for (int i = 0; i < n; i++) \ scan(name1[i], name2[i]) #define VEC2I(type, name1, name2, n) \ std::vector name1(n), name2(n); \ for (int i = 0; i < n; i++) \ scanI(name1[i], name2[i]) #define VEC3(type, name1, name2, name3, n) \ std::vector name1(n), name2(n), name3(n); \ for (int i = 0; i < n; i++) \ scan(name1[i], name2[i], name3[i]) #define VEC3I(type, name1, name2, name3, n) \ std::vector name1(n), name2(n), name3(n); \ for (int i = 0; i < n; i++) \ scanI(name1[i], name2[i], name3[i]) #define VEC4(type, name1, name2, name3, name4, n) \ std::vector name1(n), name2(n), name3(n), name4(n); \ for (int i = 0; i < n; i++) \ scan(name1[i], name2[i], name3[i], name4[i]); #define VEC4I(type, name1, name2, name3, name4, n) \ std::vector name1(n), name2(n), name3(n), name4(n); \ for (int i = 0; i < n; i++) \ scanI(name1[i], name2[i], name3[i], name4[i]); #define VV(type, name, h, w) \ std::vector> name(h, std::vector(w)); \ scan(name) #define VVI(type, name, h, w) \ std::vector> name(h, std::vector(w)); \ scanI(name) #define overload5(a, b, c, d, e, name, ...) name #define rep(i, l, r) for (int i = (l); i < (r); ++i) #define per(i, l, r) for (int i = (r - 1); i >= (l); --i) #define fore0(a) rep (a.size()) #define fore1(i, a) for (auto &&i : a) #define fore2(a, b, v) for (auto &&[a, b] : v) #define fore3(a, b, c, v) for (auto &&[a, b, c] : v) #define fore4(a, b, c, d, v) for (auto &&[a, b, c, d] : v) #define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__) #define pb push_back #define eb emplace_back #define mp std::make_pair #define ALL(x) (x).begin(), (x).end() #define UNIQUE(x) (x).erase(std::unique((x).begin(), (x).end()), (x).end()) #define fi first #define se second #define dump(...) \ std::cerr << ' '; \ std::cerr << #__VA_ARGS__ << " : [" << __LINE__ << " : " << __FUNCTION__ << "]" << std::endl; \ std::cerr << " "; \ dumper::dumpFunc(__VA_ARGS__) #pragma endregion #pragma endregion #line 4 "main.cpp" #line 1 "/Library/atcoder/lazysegtree.hpp" #line 8 "/Library/atcoder/lazysegtree.hpp" #line 1 "/Library/atcoder/internal_bit.hpp" #ifdef _MSC_VER #include #endif #if __cplusplus >= 202002L #include #endif namespace atcoder { namespace internal { #if __cplusplus >= 202002L using std::bit_ceil; #else // @return same with std::bit::bit_ceil unsigned int bit_ceil(unsigned int n) { unsigned int x = 1; while (x < (unsigned int)(n)) x *= 2; return x; } #endif // @param n `1 <= n` // @return same with std::bit::countr_zero int countr_zero(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } // @param n `1 <= n` // @return same with std::bit::countr_zero constexpr int countr_zero_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } } // namespace internal } // namespace atcoder #line 10 "/Library/atcoder/lazysegtree.hpp" namespace atcoder { #if __cplusplus >= 201703L template struct lazy_segtree { static_assert(std::is_convertible_v>, "op must work as S(S, S)"); static_assert(std::is_convertible_v>, "e must work as S()"); static_assert( std::is_convertible_v>, "mapping must work as F(F, S)"); static_assert( std::is_convertible_v>, "compostiion must work as F(F, F)"); static_assert(std::is_convertible_v>, "id must work as F()"); #else template struct lazy_segtree { #endif public: lazy_segtree() : lazy_segtree(0) {} explicit lazy_segtree(int n) : lazy_segtree(std::vector(n, e())) {} explicit lazy_segtree(const std::vector& v) : _n(int(v.size())) { size = (int)internal::bit_ceil((unsigned int)(_n)); log = internal::countr_zero((unsigned int)size); d = std::vector(2 * size, e()); lz = std::vector(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; std::vector lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; } // namespace atcoder #line 6 "main.cpp" struct MakeIOFast { MakeIOFast() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(15); } } makeIOFastv; using namespace std; int op(int a, int b) { return a + b; } int e() { return 0; } int main() { INT(N); vector ts; vector X(N); vector L(N), R(N); rep (i, 0, N) { scan(X[i], L[i], R[i]); ++R[i]; ts.pb(L[i]); ts.pb(R[i]); } INT(Q); vector Type(Q), l(Q), r(Q), t(Q); vector x(Q); rep (i, 0, Q) { scan(Type[i]); --Type[i]; if (Type[i] == 0) { scan(x[i], t[i]); ts.pb(t[i]); } if (Type[i] == 1) { scan(t[i]); ts.pb(t[i]); } if (Type[i] == 2) { scan(x[i], l[i], r[i]); ++r[i]; ts.pb(l[i]); ts.pb(r[i]); } } sort(ALL(ts)); UNIQUE(ts); map>> ma; const int M = (int)ts.size(); atcoder::lazy_segtree seg(M); rep (i, 0, N) { const int li = lwbi(ts, L[i]), ri = lwbi(ts, R[i]); seg.apply(li, ri, 1); ma[X[i]].insert({L[i], R[i]}); } rep (i, 0, Q) { if (Type[i] == 0) { auto &u = ma[x[i]]; auto itr = u.upper_bound({t[i], 1 << 30}); if (itr == u.begin()) print("No"); else if ((--itr)->second > t[i]) print("Yes"); else print("No"); } if (Type[i] == 1) { const auto p = lwbi(ts, t[i]); print(seg.get(p)); } if (Type[i] == 2) { const int li = lwbi(ts, l[i]), ri = lwbi(ts, r[i]); seg.apply(li, ri, 1); ma[x[i]].insert({l[i], r[i]}); } } }