为了方便，以下"上下左右"均基于通常的平面直角坐标系
考虑未被喂食的蚂蚁，即构成最大独立集，也即可以看作：
作一条从左上出发，不断向右/下的折线，最大化折线下方白点数+上方黑点数
由于黑点总数确定，这又等价于最大化折线下方白点数-黑点数
显然随着白点的加入，折线下方区域单调不降
对时间分治，求出\(mid\)处最优折线，则\([l,mid]\)和\((mid,r]\)分别仅需考虑折线下/上方
关于最优折线，定义\(f_{i,j}\)表示前\(i\)行\(j\)列的答案，则\(f_{i,j}=\max_{k\le j}(f_{i-1,k}+sum_{i,k})\)
维护差分数组，由于取前缀\(\max\)，\(-1\)需转化为将之后第一个正数\(-1\)（\(+1\)不变）
在此基础上，从后往前构造方案，即某次\(-1\)的区间包含\(j\)则将\(j\)调整为左端点\(-1\)
时间复杂度为\(O((n+m)\log^{2}m)\)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pii;
const int N=100005,M=(N<<1);
int n,m,x[M],y[M],id[M],mat[N],ans[N];
vector<pii>v;multiset<int>S;
multiset<int>::iterator it;
bool cmp(int i,int j){
if (x[i]!=x[j])return x[i]>x[j];
if (y[i]!=y[j])return y[i]>y[j];
return i>j;
}
void solve(int l,int r,vector<pii>v){
if (l>r)return;
int mid=(l+r>>1);S.clear();
for(pair<int,int>i:v){
if (i.se>n){
if (i.se<=n+mid)S.insert(i.fi);
}
else{
it=S.lower_bound(i.fi);
if (it==S.end())mat[i.se]=(1e9)+1;
else mat[i.se]=(*it),S.erase(it);
}
}
int now=1e9;vector<pii>vl,vr;
reverse(v.begin(),v.end());
for(pair<int,int>i:v){
if ((i.se<=n)&&(i.fi<=now)&&(now<mat[i.se]))now=i.fi-1;
if (i.fi>now)vr.push_back(i);
else{
if (i.se<n+mid)vl.push_back(i);
if (i.se<=n)ans[mid]--,ans[r+1]++;
else ans[max(i.se-n,mid)]++,ans[r+1]--;
}
}
reverse(vl.begin(),vl.end());
reverse(vr.begin(),vr.end());
solve(l,mid-1,vl),solve(mid+1,r,vr);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d%d",&x[i+n],&y[i+n]);
for(int i=1;i<=n+m;i++)id[i]=i;
sort(id+1,id+n+m+1,cmp);
for(int i=1;i<=n+m;i++)v.push_back(make_pair(y[id[i]],id[i]));
solve(1,m,v);
for(int i=1;i<=m;i++){
ans[i]+=ans[i-1];
printf("%d\n",i-ans[i]);
}
return 0;
}