今日头条第四题

#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;
}
全部评论
q此查询应该是o(qlogn)总的复杂度是O(qlogn+nlogn)
点赞 回复 分享
发布于 2017-04-05 09:48
楼主有地方写错了,树状数组sum对某个元素进行修改时: int add(int x){ while(x<maxn){ c[x]++;//这里应该改成sum[x]++; x+=lowbit(x); } }
点赞 回复 分享
发布于 2017-04-04 10:39
能不能把51nod的题号说一下,谢啦
点赞 回复 分享
发布于 2017-03-31 10:25
前端考了这题 只过了 30%
点赞 回复 分享
发布于 2017-03-30 22:48
51nod是什么
点赞 回复 分享
发布于 2017-03-30 22:42

相关推荐

身边有人上海、深圳&nbsp;6、7k&nbsp;都去了,真就带薪上班了。
程序员小白条:木的办法, 以后越来越差,还是家附近宅着吧,毕业的人越来越多,岗位都提供不出来,经济又过了人口红利期
点赞 评论 收藏
分享
不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务