今日头条第四题

#include<bits/stdc  .h>
using namespace std;
const int maxn=1e5 5;
int a[maxn],b[maxn],c[maxn];
int x[maxn],y[maxn],z[maxn];
int ans[maxn],sum[maxn];
/*
	求ai>=x&&bi>=y的个数,有q组询问
	如果保证ai>=x,那么只要保证查询bi>=y的有多少个就可以了
	把a b按照a从大到小排序
	把x y按照x从大到小排序
	这样，对于一个(xi,yi)只要把所有a>=xi的,b加入树状数组或者线段数
	就能很快的查询b>=yi的个数
	总体复杂度O((n q)logn maxn)
*/

bool cmp1(int i,int j){
	if(a[i]==a[j])return b[i]>b[j];
	return a[i]>a[j];
}
bool cmp2(int i,int j){
	if(x[i]==x[j])return y[i]>y[j];
	return x[i]>x[j];
}

int lowbit(int x){return x&(-x);}

int add(int x){
	while(x<maxn){
        sum[x]  ;
        x =lowbit(x);
    }
}

int Sum(int x){
    int ret=0;
    while(x>0){
        ret =sum[x];
        x-=lowbit(x);
    }
    return ret;
}
int main(){
	//freopen("in.txt","r",stdin);
	for(int i=1;i<maxn;i  )c[i]=i,z[i]=i;
	int n,q;
	cin>>n>>q;
	for(int i=0;i<n;i  )cin>>a[i];
	for(int i=0;i<n;i  )cin>>b[i];
	sort(c,c n,cmp1);
	
	//离线
	for(int i=0;i<q;i  )cin>>x[i]>>y[i];
	sort(z,z q,cmp2);
	
	int top=0;
	
	for(int i=0;i<q;i  ){
		while(top<n&&a[c[top]]>=x[z[i]])add(b[c[top  ]]);
		ans[z[i]]=top-Sum(y[z[i]]-1);
	}
	
	for(int i=0;i<q;i  )
		cout<<ans[i]<<endl;
	
	return 0;
}