1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e5+5; 4 int a[maxn],b[maxn],c[maxn]; 5 int x[maxn],y[maxn],z[maxn]; 6 int ans[maxn],sum[maxn]; 7 /* 8     求ai>=x&&bi>=y的个数,有q组询问 9     如果保证ai>=x,那么只要保证查询bi>=y的有多少个就可以了10     把a b按照a从大到小排序11     把x y按照x从大到小排序12     这样，对于一个(xi,yi)只要把所有a>=xi的,b加入树状数组或者线段数13     就能很快的查询b>=yi的个数14     n个数插入树状数组一次，复杂度O(nlogn)15     总共查询q次，复杂度O(nlogn)16     总体复杂度O(nlogn)17 */18 19 bool cmp1(int i,int j){20     if(a[i]==a[j])return b[i]>b[j];21     return a[i]>a[j];22 }23 bool cmp2(int i,int j){24     if(x[i]==x[j])return y[i]>y[j];25     return x[i]>x[j];26 }27 28 int lowbit(int x){return x&(-x);}29 30 int add(int x){31     while(x<maxn){32         c[x]++;33         x+=lowbit(x);34     }35 }36 37 int Sum(int x){38     int ret=0;39     while(x>0){40         ret+=sum[x];41         x-=lowbit(x);42     }43     return ret;44 }45 int main(){46     //freopen("in.txt","r",stdin);47     for(int i=1;i<maxn;i++)c[i]=i,z[i]=i;48     int n,q;49     cin>>n>>q;50     for(int i=0;i<n;i++)cin>>a[i];51     for(int i=0;i<n;i++)cin>>b[i];52     sort(c,c+n,cmp1);53     54     //离线55     for(int i=0;i<q;i++)cin>>x[i]>>y[i];56     sort(z,z+q,cmp2);57     58     int top=0;59     60     for(int i=0;i<q;i++){61         while(top<n&&a[c[top]]>=x[z[i]])add(b[c[top++]]);62         ans[z[i]]=top-Sum(y[z[i]]-1);63     }64     65     for(int i=0;i<q;i++)66         cout<<ans[i]<<endl;67     68     return 0;69 }