自搬

原文哦

---

看见没有 01Trie 的，赶紧来交一篇。

题意简述

笔和笔盖分别有两个属性 $x$ 和 $y$，$y$ 相同的笔和笔盖可以组成配对，$x$ 和 $y$ 都相同的笔和笔盖可以组成优秀的配对。问最多有几个配对，几个优秀的配对。

思路

配对很简单，开两个桶，把不同东西的 $y$ 分别统计一下，答案就是 $\sum\min(b_1(i),b_2(i))$。

优秀的配对虽然也可以开桶，但是如果数据范围再大一点就会爆空间。发现桶的大部分空间都被浪费，这个时候我们就可以用到 map 了。然而 map 常数略大，更好的选择是动态开点的字典树。对于每一个物品，我们把它的两个属性压进一个 int，然后扔进一个 01Trie，就能优美地统计优秀的配对了。

实现

动态开点字典树可以用数组模拟。

#include<cstdio>
#include<cstring>
using namespace std;

#define ll long long
#define ull unsigned long long
namespace io{
	const int size=(1<<20)+1;
	char buf[size],*p1=buf,*p2=buf;
	char buffer[size];
	int op1=-1;
	const int op2=size-1;
	
	inline char readchar() {
		if(p1!=p2) {
			return *p1++;
		}
		return p1==(p2=(p1=buf)+fread(buf,1,size-1,stdin))?EOF:*p1++;
	}
	
	inline void flush() {
		fwrite(buffer,1,op1+1,stdout),op1=-1;
	}
	
	inline void writechar(const char &x) {
		if(op1==op2) flush();
		buffer[++op1]=x;
	}
	#define gc readchar
	#define pc writechar
	#define el pc(10)
	#define sp pc(32)
	
	template<typename Tp>
	inline Tp read(){
		Tp x=0;
		bool w=0;
		char ch=gc();
		while(ch<'0'||ch>'9')ch=='-'&&(w=1),ch=gc();
		while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gc();
		return x;
	}
	
	template<typename Tp>
	void write(Tp x){
		if(x<0)pc('-'),x=-x;
		if(x>9)write(x/10);
		pc((x%10)^48);
	}
};
using namespace io;

struct node{
	int l,r,v,v2;
}t[2000005];
int tcnt;

struct node2{
	int v,v2;
}b[1005];

#define newnode (++tcnt)
#define s(x,y) ((x)<<10)|(y)

void add(int k,int v){
	if(!v){
		t[k].v++;
		return;
	}
	if(v&1){ // 1->r
		if(t[k].r) add(t[k].r,v>>1);
		else t[k].r=newnode,add(t[k].r,v>>1);
	}else{ // 0->l
		if(t[k].l) add(t[k].l,v>>1);
		else t[k].l=newnode,add(t[k].l,v>>1);
	}
}

void add2(int k,int v){
	if(!v){
		t[k].v2++;
		return;
	}
	if(v&1){ // 1->r
		if(t[k].r) add2(t[k].r,v>>1);
		else t[k].r=newnode,add2(t[k].r,v>>1);
	}else{ // 0->l
		if(t[k].l) add2(t[k].l,v>>1);
		else t[k].l=newnode,add2(t[k].l,v>>1);
	}
}

template<typename Tp>
inline const Tp& min(const Tp& x,const Tp& y){
	return x<y?x:y;
}

int main(){
	int n=read<int>(),m=read<int>();
	newnode;
	for(int i=1;i<=n;i++){
		int x,y;
		x=read<int>(),y=read<int>();
		add(1,s(x,y));
		b[y].v++;
	}
	
	for(int i=1;i<=m;i++){
		int x,y;
		x=read<int>(),y=read<int>();
		add2(1,s(x,y));
		b[y].v2++;
	}
	
	int cnt=0;
	for(int i=1;i<=1000;i++){
		cnt+=min(b[i].v,b[i].v2);
	}
	write(cnt);sp;
	
	cnt=0;
	for(int i=1;i<=2000000;i++){
		cnt+=min(t[i].v,t[i].v2);
	}
	write(cnt);el;
	
	flush();
	return 0;
}