首先先簡(jiǎn)化一下題意，更改最少的籍貫使得\(A\)集合中每個(gè)數(shù)都能與\(B\)集合中的數(shù)一一配對(duì)；

我們發(fā)現(xiàn)，只修改一個(gè)集合即可，這里假設(shè)只修改\(B\)集合，考慮如下情景:

兩集合均從小到大排好序
有\(len\)個(gè)數(shù)小于等于\(b_{pos}\)，我們要把這\(len\)個(gè)\(a\)和\(pos\)個(gè)\(b\)配對(duì)

我們稱\(pos\)及其左邊為內(nèi)部，\(pos\)右邊為外部
每個(gè)\(a_i\)只有兩種情況，一種和外部配對(duì)，一種和內(nèi)部配對(duì)，設(shè)配對(duì)到外部的個(gè)數(shù)為\(x\)

考慮一種情況是合法的，當(dāng)且僅當(dāng)對(duì)于每個(gè)\(pos\)，都有\(len-x \geq pos\)，這樣才能保證有足夠的數(shù)與\(b_1\sim b_{pos}\)都有數(shù)與之配對(duì)，即\(x\leq len-pos\)

如果理解上面的那些，我們就可以來(lái)想一個(gè)\(60 pts\)的\(n^2\)暴力（實(shí)際去捆綁后是96），對(duì)于每一個(gè)\(b\),我們貪心地從還沒(méi)被配對(duì)的籍貫相同的\(a_j\)配對(duì)，然后判斷滿不滿足條件，我們發(fā)現(xiàn)關(guān)鍵在于找到\(a_j--b_{i}\)這組配對(duì)作為哪些pos的外部，事實(shí)上與下列兩個(gè)條件互為充要：
①\(a_j\leq b_{pos}\)
②\(pos \lt i\)

于是我們暴力維護(hù)即可，滿分做法即用線段樹(shù)維護(hù)，葉子結(jié)點(diǎn)初值即為\(len-pos\)
鑒于筆者暫不清楚讀者水平，在此貼一下代碼，有一些細(xì)節(jié)沒(méi)在上面講，在代碼中指出，讀者可以自己思考一下為什么

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 500;
int read() {
	int x=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}

vector<int > p[N];
int n,l[N],pos[N],siz[N],t[N<<2],tag[N<<2];
struct node {
	int id,w;
}a[N],b[N];

void push_up(int p) { t[p]=min(t[p<<1],t[p<<1|1]); }

void build(int p,int l,int r) {
	if(l==r) {
		t[p]=siz[l];return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	push_up(p);
}

void push_down(int p) {
	if(tag[p]!=0) {
		tag[p<<1]+=tag[p],tag[p<<1|1]+=tag[p];
		t[p<<1|1]+=tag[p],t[p<<1]+=tag[p];
		tag[p]=0;
	}
}

void update(int p,int l,int r,int x,int y,int k) {
	if(x>y) return ;//可能會(huì)有越界
	if(x<=l&&r<=y) {
		tag[p]+=k,t[p]+=k;return ;
	}
	push_down(p);
	int mid=l+r>>1;
	if(x<=mid) update(p<<1,l,mid,x,y,k);
	if(y>mid) update(p<<1|1,mid+1,r,x,y,k);
	push_up(p);
}

signed main() {
    cin>>n;
    for(int i=n;i>=1;i--) a[i].id=read(),a[i].w=read();
    for(int i=n;i>=1;i--) b[i].id=read(),b[i].w=read();
    int nw=0;
	for(int i=1;i<=n;i++) {
		l[i]=l[i-1];
    	while(nw<n&&a[nw+1].w<=b[i].w) nw++,l[i]=nw,pos[nw]=i;
    	siz[i]=l[i]-i;
    }
    int ans=0;build(1,1,n);
    for(int i=1;i<=n;i++) {
    	for(int j=l[i-1]+1;j<=l[i];j++) p[a[j].id].push_back(j);
    	if(p[b[i].id].empty()) continue;
    	int r=pos[p[b[i].id].back()];//要取最靠近的，想想為啥
    	update(1,1,n,r,i-1,-1);
    	if(t[1]<0) update(1,1,n,r,i-1,1);
    	else ans++,p[b[i].id].pop_back();p[b[i].id].pop_back(),ans++;
    }
    cout<<n-ans;
    return 0;
}`