前言
认认真真学习了一下这道题相关的做法以及有关的二分图网络流理论，感觉自己又刷新了一些东西的理解。
所以说我们就从普通的二分图匹配开始吧！
二分图匹配
众所周知，二分图最大匹配可以用网络流 Dinic 算法做到 \(O(m\sqrt n)\) 的复杂度。
在某些特定的图下，我们有一种“贪心流”算法。
由于 zhy 喜欢反反复复提到这个东西，所以在平时我也会经常去有限考虑某道题目能否转化成贪心流问题
再探柯尼希定理
本题题意
给定
#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
int read(){/*...*/}
const int N=200003;
int n,m;
struct Pos{
int x,y,id;
friend bool operator<(const Pos a,const Pos b){
if(a.x!=b.x) return a.x<b.x;
if(a.y!=b.y) return a.y<b.y;
return a.id<b.id;
}
}s[N],sl[N],sr[N];
int res[N],mat[N];
void solve(int vl,int vr,int l,int r,int cur){
if(vl>vr) return;
int mid=(vl+vr)>>1;
multimap<int,int> mp;
for(int i=r;i>=l;--i)
if(s[i].id){
if(s[i].id<=mid) mp.emplace(s[i].y,i);
}
else{
auto it=mp.lower_bound(s[i].y);
if(it==mp.end()){mat[i]=0;continue;}
mat[i]=it->second;
mp.erase(it);
}
int lef=0,nl=0;
int rig=0,nr=0;
int lim=0x3f3f3f3f;
for(int i=l;i<=r;++i){
if(s[i].id){
if(s[i].id<=mid&&s[i].y<lim) sl[++nl]=s[i],++lef;
else sr[++nr]=s[i];
}
else{
if(!mat[i]||s[mat[i]].y>=lim) lim=min(lim,s[i].y);
if(s[i].y>=lim) sr[++nr]=s[i],++rig;
else sl[++nl]=s[i];
}
}
for(int i=1;i<=nl;++i) s[l+i-1]=sl[i];
for(int i=1;i<=nr;++i) s[l+nl+i-1]=sr[i];
res[mid]=lef+rig+cur;
solve(vl,mid-1,l,l+nl-1,cur+rig);
solve(mid+1,vr,r-nr+1,r,cur+lef);
}
int main(){
n=read();
for(int i=1;i<=n;++i){s[i].x=read();s[i].y=read();s[i].id=0;}
m=read();
for(int i=1;i<=m;++i){s[i+n].x=read();s[i+n].y=read();s[i+n].id=i;}
sort(s+1,s+n+m+1);
solve(1,m,1,n+m,0);
for(int i=1;i<=m;++i) printf("%d\n",n+i-res[i]);
return 0;
}