#include using namespace std; #define overload2(a, b, c, ...) c #define overload3(a, b, c, d, ...) d #define overload4(a, b, c, d, e ...) e #define overload5(a, b, c, d, e, f ...) f #define overload6(a, b, c, d, e, f, g ...) g #define fast_io ios::sync_with_stdio(false); cin.tie(nullptr); #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") typedef long long ll; typedef long double ld; #define chmin(a,b) a = min(a,b); #define chmax(a,b) a = max(a,b); #define bit_count(x) __builtin_popcountll(x) #define leading_zero_count(x) __builtin_clz(x) #define trailing_zero_count(x) __builtin_ctz(x) #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a / gcd(a,b) * b #define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__) #define rep1(i,n) for(int i = 0 ; i < n ; i++) #define rrep(i,a,b) for(int i = a ; i < b ; i++) #define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++) #define pt(a) cout << a << endl; #define print(...) printall(__VA_ARGS__); #define debug(a) cout << #a << " " << a << endl; #define all(a) a.begin(), a.end() #define endl "\n"; #define v1(T,n,a) vector(n,a) #define v2(T,n,m,a) vector>(n,v1(T,m,a)) #define v3(T,n,m,k,a) vector>>(n,v2(T,m,k,a)) #define v4(T,n,m,k,l,a) vector>>>(n,v3(T,m,k,l,a)) templateistream &operator>>(istream&is,pair&p){is>>p.first>>p.second;return is;} templateostream &operator<<(ostream&os,const pair&p){os<istream &operator>>(istream&is,vector&v){for(T &in:v){is>>in;}return is;} templateostream &operator<<(ostream&os,const vector&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} templateistream &operator>>(istream&is,vector>&v){for(T &in:v){is>>in;}return is;} templateostream &operator<<(ostream&os,const vector>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;} templateostream &operator<<(ostream&os,const set&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} templateostream &operator<<(ostream&os,const multiset&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;} template void printall(Args... args){for(auto i:initializer_list>{args...}) cout< struct Compress{ private: vector vec ; // 元の値の座標圧縮後の値 unordered_map mp ; // 元の値 -> 変換された値 unordered_map np ; // 変換された値 -> 元の値 void build(vector A){ int n = A.size() ; vector B(n) ; for(int i = 0 ; i < n ; i++) B[i] = A[i] ; vec.resize(n) ; sort(A.begin(),A.end()) ; for(int i = 0 ; i < n ; i++){ auto it = lower_bound(A.begin(),A.end(),B[i]) ; int id = it - A.begin() ; vec[i] = id ; mp[B[i]] = id; np[id] = B[i] ; } } public: Compress(){} Compress(vector A) { build(A); } size_t size() {return vec.size() ; } // 元の値 -> 変換された値 inline int encrypt(T i) { return mp[i] ; } // 変換された値 -> 元の値 inline T decrypt(int i) { return np[i] ; } vector compress() { return vec; } vector compress(vector A) { build(A); return vec; } inline int operator [] (int i) { return vec[i] ; } }; // function : return : description // ----------------------------------------------------- // Compress() : void : コンストラクタ // Compress(vector A) : void : コンストラクタ, 座圧する // encrypt(ll v) : int : 元の値 -> 座圧後の値 // decrypt(int v) : ll : 座圧後の値 -> 元の値 // compress() : vector : 座圧後の値 // operator[i] : int : 座圧後の値の vector にアクセスすることが可能 template struct LazySegmentTree{ private : const ll linf = 1e18 ; const int inf = 1e8 ; int n , n_ ; vector dat , lazy ; void build(){ n = 1 ; while(n < n_) n *= 2 ; dat.resize(2*n-1,0) ; lazy.resize(2*n-1,0) ; } // 遅延評価 void eval(int k){ dat[k] += lazy[k] ; if(k < n - 1){ lazy[2 * k + 1] += lazy[k] / 2 ; lazy[2 * k + 2] += lazy[k] / 2 ; } lazy[k] = 0 ; } // 区間加算 void add_(int a , int b , int k , int l , int r , T w){ eval(k) ; if(b <= l || r <= a) return ; if(a <= l && r <= b) { // 区間加算 lazy[k] += (r - l) * w ; eval(k) ; return ; } add_(a,b,2*k+1,l,(l+r)/2,w) ; add_(a,b,2*k+2,(l+r)/2,r,w) ; // 区間の更新をする必要がある dat[k] = dat[2*k+1] + dat[2*k+2] ; } void add_(int a , int b , T x){ return add_(a,b,0,0,n,x) ; } T query_(int a , int b , int k , int l , int r){ //遅延評価(これは確実に必要) eval(k) ; if(b <= l || r <= a) return 0 ; if(a <= l && r <= b) return dat[k] ; T lef = query_(a,b,2*k+1,l,(l+r)/2) ; T rig = query_(a,b,2*k+2,(l+r)/2,r) ; return lef + rig ; } T query_(int a , int b){ return query_(a,b,0,0,n) ; } public : LazySegmentTree(int _n) : n_(_n) { build() ; } T query(int a , int b) { return query_(a,b) ; } void add(int a , int b , T x) { add_(a,b,x) ; } }; int n; void solve(){ cin >> n; map>> mp; vector V; rep(i,n){ string s; int l, r; cin >> s >> l >> r; V.push_back(l); V.push_back(r); mp[s].insert({l,r}); } int q; cin >> q; vector> Q(q); rep(i,q){ int t; cin >> t; if(t == 1){ string s; int x; cin >> s >> x; Q[i] = {i,t,x,-1,s}; V.push_back(x); } if(t == 2){ int x; cin >> x; Q[i] = {i,t,x,-1,""}; V.push_back(x); } if(t == 3){ string s; int l, r; cin >> s >> l >> r; Q[i] = {i,t,l,r,s}; V.push_back(l); V.push_back(r); } } Compress C(V); LazySegmentTree segtree(C.size()); for(auto [key,vec] : mp){ for(auto[l,r]:vec){ auto lv = C.encrypt(l); auto rv = C.encrypt(r); segtree.add(lv,rv+1,1); } } rep(i,q){ auto[id,t,l,r,s] = Q[i]; if(t == 1){ auto x = l; auto it = mp[s].upper_bound({x,1e9}); bool ok = false; if(it != mp[s].begin()){ it--; ok = (x <= (*it).second); } if(ok) {pt("Yes")} else {pt("No")} } if(t == 2){ auto x = l; auto xv = C.encrypt(x); pt(segtree.query(xv,xv+1)) } if(t == 3){ auto lv = C.encrypt(l); auto rv = C.encrypt(r); segtree.add(lv,rv+1,1); mp[s].insert({l,r}); } } } int main(){ fast_io int t = 1; // cin >> t; rep(i,t) solve(); }