为啥网上这题很少有题解啊。
首先，改 A 和改 C 是一样的，我们考虑只改 C。让 D 去匹配 B。
有一个比较好想的做法，先考虑能够同国匹配的就先匹配掉（这个可以用 multiset），剩余的，考虑按值域来（实际上离散化后就是跟按序列一样），对于 $D_i$，那么所对应 $B_j$ 的值域在 $[D_i,max]$。
那么，分成 2 个部分，将 D 部的 $i$ 连向 B 部的 $[D_i,max]$ 这些点。那么，我们只需要看看有没有完美匹配即可。
假如同国匹配的全都匹配掉之后再去看看有没有完美匹配，则可能不行。
我们要让最后一定有完美匹配，所以对于同国能匹配的，还要判断删去 D 部这个点，还能不能形成完美匹配。
但这样复杂度是 $O(n^2sqrt{n})$ 级别的。
考虑只需要判断有没有，想到 hall 定理。
即 $|could(S)|-|S|ge 0$。
按照套路维护前缀 $|could(S)|,|S|$。对于 $D_i$，那么会对 $|S|$ 有贡献（我们是让 D 部匹配 B 部嘛）贡献范围是 $[D_i,max]$ （前缀集合大小贡献），对于 $B_i$，对 $|could(S)|$ 有贡献，贡献范围是 $[B_i,max]$，即对于 $D_j in [B_i,max]$，才可能匹配它。
这个样子相当于 $+-1$，用线段树维护前缀最小值即可。（注意是前缀，因为要表示子集！！！为什么可以看另一道相似的题目的题解）
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define ll long long
using namespace std;
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
ll lrd() {
ll f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
/*
考虑改A和改C没区别
让结束的这一部去匹配之前的那一部
且维护线段树前缀和，这时对于点数就不一定是 l 了
可以考虑动态加
*/
#define ls (cur<<1)
#define rs (ls|1)
#define int ll
const int N=(int)(5e5+5);
multiset<int>s[N];
multiset<int>::iterator it;
int mi[N<<2],tag[N<<2],A[N],B[N],C[N],D[N],lsh[N<<1],tot,n;
void push_up(int cur) {
mi[cur]=min(mi[ls],mi[rs]);
}
void push_down(int cur) {
if(!tag[cur]) return ;
tag[ls]+=tag[cur]; tag[rs]+=tag[cur];
mi[ls]+=tag[cur]; mi[rs]+=tag[cur];
tag[cur]=0;
}
void update(int cur,int l,int r,int cl,int cr,int v) {
if(cl<=l&&r<=cr) return mi[cur]+=v,tag[cur]+=v,void();
push_down(cur);
int mid=(l+r)>>1;
if(cl<=mid) update(ls,l,mid,cl,cr,v);
if(cr>mid) update(rs,mid+1,r,cl,cr,v);
push_up(cur);
}
signed main() {
n=rd();
for(int i=1;i<=n;i++) A[i]=rd(),B[i]=rd(),lsh[++tot]=B[i];
for(int i=1;i<=n;i++) C[i]=rd(),D[i]=rd(),lsh[++tot]=D[i];
sort(lsh+1,lsh+1+tot); tot=unique(lsh+1,lsh+1+tot)-lsh-1;
for(int i=1;i<=n;i++) {
B[i]=lower_bound(lsh+1,lsh+1+tot,B[i])-lsh; D[i]=lower_bound(lsh+1,lsh+1+tot,D[i])-lsh;
s[A[i]].insert(B[i]);
update(1,1,tot,B[i],tot,1); //匹配的点数，只能是之后的
update(1,1,tot,D[i],tot,-1); //前缀的集合+1
}
int ans=0;
for(int i=n;i>=1;i--) {
it=s[C[i]].upper_bound(D[i]);
if(it==s[C[i]].begin()) ++ans;
else {
--it; int qwq=*it;
s[C[i]].erase(it);
update(1,1,tot,qwq,tot,-1); update(1,1,tot,D[i],tot,1);
if(mi[1]<0) { //剩下的没有完美匹配
s[C[i]].insert(qwq); ++ans;
update(1,1,tot,qwq,tot,1); update(1,1,tot,D[i],tot,-1);
}
}
}
printf("%lld",ans); return 0;
}