2 2 1 2 3 4 2 3 4 5 3 2 3 5 7 6 8 4 1 2 5 3 4
1 2
#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define lson L,mid,ls
#define rson mid+1,R,rs
const int maxn=100010;
int num[maxn<<3];//离散化后有2*n忘了改大空间了。坑
struct node
{
int w,h;
} ag[maxn],bg[maxn];
int H[maxn<<1];
inline bool cmp(const node &a,const node &b)
{
if(a.w==b.w)
return a.h<b.h;
return a.w<b.w;
}
void build(int L,int R,int rt)
{
num[rt]=0;
if(L==R)
return ;
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
build(lson);
build(rson);
}
void update(int L,int R,int rt,int p,int d)
{
if(L==R)
{
num[rt]+=d;
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(p<=mid)
update(lson,p,d);
else
update(rson,p,d);
num[rt]=num[ls]+num[rs];
}
int qu(int L,int R,int rt,int p)
{
if(!num[rt])
return -1;
if(L==R)
return L;
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1,pos=-1;
if(p<=mid)
return qu(lson,p);
if(num[rs])
pos=qu(rson,p);
if(pos!=-1)
return pos;
return qu(lson,p);
}
int main()
{
int t,n,i,m,p,ans;
scanf("%d",&t);
while(t--)
{
m=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&ag[i].h,&ag[i].w);
H[m++]=ag[i].h;
}
for(i=0;i<n;i++)
{
scanf("%d%d",&bg[i].h,&bg[i].w);
H[m++]=bg[i].h;
}
sort(ag,ag+n,cmp);
sort(bg,bg+n,cmp);
sort(H,H+m);
m=unique(H,H+m)-H;
build(1,m,1);
ans=p=0;
for(i=0;i<n;i++)
{
while(p<n&&bg[p].w<=ag[i].w)
update(1,m,1,lower_bound(H,H+m,bg[p].h)-H+1,1),p++;
int pos=qu(1,m,1,lower_bound(H,H+m,ag[i].h)-H+1);
if(pos!=-1)
{
ans++;
update(1,m,1,pos,-1);
}
}
printf("%d\n",ans);
}
return 0;
}
hdu 4268 Alice and Bob(multiset|线段树)
原文:http://blog.csdn.net/bossup/article/details/40585091