#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair P; typedef pair PP; const ll MOD=1e9+7; struct Query{ int type; string x; int t; int l; int r; }; int op(int x, int y){ //(x,y)を比較する任意の演算子.今回はmaxとした return (x+y); } int e(){ //initialize value return 0; } template class segment_tree{ public: std::vector dat; int n=1; segment_tree(int n_){ while(n < n_){ n*=2; } dat = std::vector(2*n-1,e());// 0,1,2,...,2*n-1,2*n-2 } ~segment_tree(){ std::vector().swap(dat); } void set(int k,Type a){ update(k,a); } void update(int k,Type a){ k+=n-1; dat[k] = a; while(k>0){ k = (k-1)/2; dat[k]=op(dat[2*k+1],dat[2*k+2]); } } //[a,b) Type query(int a,int b,int k,int l,int r){ if(r<=a || b<=l) return e(); if(a<=l && r<=b) return dat[k]; else{ Type vl = query(a,b,2*k+1,l,(l+r)/2); Type vr = query(a,b,2*k+2,(l+r)/2,r); return op(vl,vr); } } //[a,b)の範囲でのmax Type query(int a,int b){ return query(a,b,0,0,n); } Type operator[](int index){ return get(index); } Type get(int index){ index += n-1; return dat[index]; } void add(int k,Type a){ Type c=get(k); update(k,c+a); } }; struct LazySegmentTree { private: int n; vector node, lazy; public: LazySegmentTree(vector v) { int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1); lazy.resize(2*n-1, 0); for(int i=0; i=0; i--) node[i] = node[i*2+1] + node[i*2+2]; } //k番目のノードについて遅延評価を行う void eval(int k, int l, int r) { //遅延配列が空でない場合 自分のノード及び子ノードへの値の伝播が起こる if(lazy[k] != 0) { node[k] += lazy[k]; if(r - l > 1) {//[l,r) lazy[2*k+1] += lazy[k] / 2; lazy[2*k+2] += lazy[k] / 2; } lazy[k] = 0;//伝播が終わったので自分のノードの遅延配列を0にする } } //[l,r)かな void add(int a, int b, ll x, int k=0, int l=0, int r=-1) { if(r < 0) r = n; //k番目のノードに対して遅延評価を行う eval(k, l, r); if(b <= l || r <= a) return;//範囲外なら何もしない //完全に被覆しているならば,遅延配列に値を入れた後に評価 if(a <= l && r <= b) { lazy[k] += (r - l) * x; eval(k, l, r); } else {//そうでないならば 子ノードの値を再帰的に計算しえ計算済みの値をもらってくる add(a, b, x, 2*k+1, l, (l+r)/2); add(a, b, x, 2*k+2, (l+r)/2, r); node[k] = node[2*k+1] + node[2*k+2]; } } ll getsum(int a, int b, int k=0, int l=0, int r=-1) { if(r < 0) r = n; eval(k, l, r);//関数が呼び出されたら評価する if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; ll vl = getsum(a, b, 2*k+1, l, (l+r)/2); ll vr = getsum(a, b, 2*k+2, (l+r)/2, r); return vl + vr; } }; int main(){ int N; cin>>N; vector people; //map> mp; map mp; vector ranges; for(int i=0;i>x>>l>>r; mp[x]={l,r}; ranges.push_back(l); ranges.push_back(r); } int Q; cin>>Q; vector queries(Q); for(int q=0;q>type; if(type==1){ string x; int t; cin>>x>>t; queries[q].type=1; queries[q].x=x; queries[q].t=t; }else if(type==2){ int t; cin>>t; queries[q].type=2; queries[q].t=t; }else{ //type=3 string x; int l,r; cin>>x>>l>>r; queries[q].type=3; queries[q].x=x; queries[q].l=l; queries[q].r=r; ranges.push_back(l); ranges.push_back(r); } } set st(ranges.begin(),ranges.end()); map compress; int sz=1; for(int v:st){ compress[v]=sz; sz++; } //segment_tree seg(sz+3); LazySegmentTree seg(vector(sz+3,0)); for(auto [x,p]:mp){ auto [l,r]=p; seg.add(l,r+1,1); //seg.add(compress[l],1); //seg.add(compress[r]+1,-1); } for(int q=0;q