#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef unsigned long long int ulint; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase #define RE return 0 //ios::sync_with_stdio(false); //std::cin.tie(0); //<< setprecision(20) const int mod=(int)1e9+7; const llint big=(llint)(2.19e15+1)*18; const long double pai=3.141592653589793238462643383279502884197; const long double ena=2.71828182845904523536; const long double eps=1e-7; template bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;} template bool maxeq(T& a,U b){if(a void soun(T& ar) {sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());} llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}} llint lcm(llint a,llint b){return a/gcd(a,b) *b;} template auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);} template auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);} template auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();} template auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();} template void SO(T& ve){sort(ve.begin(),ve.end());} template void REV(T& ve){reverse(ve.begin(),ve.end());} class seg{ public: vector val; seg(void){val.res(262144);} void cha(int bas,int hen){//bas以上の要素をhen足す bas+=131072;bas--; while(bas>0){ if(bas%2==0){val[bas+1]+=hen;} bas/=2; } } int ask(int bas){ bas+=131072; int ans=0; while(bas>0){ans+=val[bas];bas/=2;} return ans; } }; int main(void){ //セグ木で殴る問題集 セグ木を使うことにより、O(m+nlog(n+m))になり、早くなります //まず座圧します int i,n,m;cin>>n; vector>aaa;//人と明太子を合わせてソート for(i=0;i>a>>b; aaa.pub(mt(a,mod,b)); } cin>>m; for(i=0;i>x>>y; aaa.pub(mt(x,i,y)); } SO(aaa);REV(aaa); vectoratu(n+m);//辛さを座圧します for(i=0;i(aaa[i]);} soun(atu); vectorans(m); seg ki; for(i=0;i(aaa[i]));qu=get<1>(aaa[i]); if(qu==mod){ki.cha(ka,1);}//人 else{ans[qu]=ki.ask(ka);} } int sai=0; for(i=0;i