C++14(g++5.4) 解法, 执行用时: 299ms, 内存消耗: 5080K, 提交时间: 2020-06-21 18:21:28

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1000;
int n,m;
struct node
{
	int x,y,id;
}a[N];
int b[N];
int cnt[N];
int c[N];
int lowbit(int x)
{
	return x&(-x);
}
void add(int i,int x)
{
	while(i<N) c[i]+=x,i+=lowbit(i);
}
int sum(int i)
{
	int res=0;
	while(i)
	{
		res+=c[i];
		i-=lowbit(i);
	}
	return res;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n+m;i++)
	{
		cin>>a[i].x>>a[i].y;
		if(i<=n ) a[i].id=0;
		else a[i].id=i-n;
		b[i]=a[i].y;
	}
	sort(a+1,a+1+n+m,[](node a,node b){
		if(a.x==b.x) return a.y<b.y;
		return a.x<b.x;
	});
	sort(b+1,b+1+n+m);
	int k=unique(b+1,b+1+n+m)-(b+1);
	for(int i=1;i<=n+m;i++)
	{
		int pos=lower_bound(b+1,b+1+k,a[i].y)-b;
		if(a[i].id==0) 
		{
			add(pos,1);
		}
		else 
		{
			cnt[a[i].id]=sum(pos);
		}
	}
	for(int i=1;i<=m;i++)
	{
		cout<<cnt[i]<<endl;
	}
	
}

C++(clang++11) 解法, 执行用时: 80ms, 内存消耗: 6152K, 提交时间: 2021-02-22 08:55:29

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int Y[N<<2],cnt;
struct node{
	int x,y,id;
	bool operator<(const node &A){
		if(x==A.x) return y<A.y;
		return x<A.x;
	}
}a[N<<2];
int ans[N];
int c[N<<2];
int lowbit(int x){
	return x&(-x);
}
void add(int x){
	for(int i=x;i<=cnt;i+=lowbit(i))
	c[i]+=1;
}
int getsum(int x){
	int res=0;
	while(x){
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n+m;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
		Y[i]=a[i].y;
		(i>n)?a[i].id=i-n:a[i].id=0;
	}
	sort(Y+1,Y+1+m+n);
	sort(a+1,a+1+m+n);
	int d=unique(Y+1,Y+1+n+m)-Y-1;
	cnt=d;
	
	for(int i=1;i<=n+m;i++){
		int p=lower_bound(Y+1,Y+1+d,a[i].y)-Y;
		if(!a[i].id) add(p);
		else ans[a[i].id]=getsum(p);
	}
	for(int i=1;i<=m;i++)
	cout<<ans[i]<<"\n";
	return 0;
}