前言
认认真真学习了一下这道题相关的做法以及有关的二分图网络流理论，感觉自己又刷新了一些东西的理解。
所以说我们就从普通的二分图匹配开始吧！
二分图匹配
众所周知，二分图最大匹配可以用网络流 Dinic 算法做到 \(O(m\sqrt n)\) 的复杂度。在某些特定的
再探柯尼希定理
本题题意
给定
#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;
}