题目
n列n行(n<=2e5)的棋盘，第k(1<=k<=n)列是特殊列，
以下有m(m<=2e5)个操作，每次给出一个兵(x,y)(x列y行)，
如果棋盘这个位置有兵，就拿掉原位置的兵，否则把它放入这个位置
兵的行走规则是可以从(x,y)走向(x,y+1),(x+1,y+1),(x-1,y+1)，
即以走向下一行为代价，保持列不变或走向相邻列
对于每次操作后，都询问一次，
若令当前棋盘上的所有兵都走到第k列上，棋盘最少需要扩充多少行
思路来源
https://www.cnblogs.com/limil/p/13204543.html
题解
首先，棋子走到第k列时，行的下限为y+abs(x-k)，称其为必要位置，大于等于该行的行也可
类似一个第几分钟有几个人排队，一分钟只能结账一个人，最终问所有人都能结账完的最小时间问题，
该问题需要动态维护，考虑Hall定理，先把所有棋子都放到必要位置，
设为第j行及第j行下方的棋子个数(即棋子位于列r，且r>=j)，
若最终棋盘共x行，则需要对任意f(j)>0的行，满足，
有，即，再减去n就是需要扩充的行数
于是开一个set<ll>cell维护哪些点在棋盘上，开一个set<ll>now维护当前移动到第k列的棋子所占的位置，
后者用于求移动到第k列的棋子的最大位置pos，pos是满足f(j)>0的最大的j
插入位置为j时，[1,j]的f(j)+1，删除同理
询问时，若now为空返回0，否则询问[1,pos]的最大值x，减n之后就是答案
由于(n,n)走到特殊列k=1时，关键位置为第2n-1行，所以开2*n的线段树
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+10;
int n,k,m,x,y,num[N],pos;
set<ll>cell,now;
struct segtree{
int n;
struct node{int l,r,v,add;}e[N<<2];
#define l(p) e[p].l
#define r(p) e[p].r
#define v(p) e[p].v
#define a(p) e[p].add
void up(int p){v(p)=max(v(p<<1),v(p<<1|1));}
void bld(int p,int l,int r){
l(p)=l;r(p)=r;
if(l==r){v(p)=l-1;return;}
int mid=l+r>>1;
bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
up(p);
}
void init(int _n){n=_n;bld(1,1,n);}
void psd(int p){
if(a(p)){
a(p<<1)+=a(p),a(p<<1|1)+=a(p);
v(p<<1)+=a(p),v(p<<1|1)+=a(p);
a(p)=0;
}
}
void chg(int p,int ql,int qr,int v){
if(ql<=l(p)&&r(p)<=qr){
a(p)+=v;
v(p)+=v;
return;
}
psd(p);
int mid=l(p)+r(p)>>1;
if(ql<=mid)chg(p<<1,ql,qr,v);
if(qr>mid)chg(p<<1|1,ql,qr,v);
up(p);
}
int ask(int p,int ql,int qr){
if(ql<=l(p)&&r(p)<=qr)return v(p);
psd(p);
int mid=l(p)+r(p)>>1,res=0;
if(ql<=mid)res=max(res,ask(p<<1,ql,qr));
if(qr>mid)res=max(res,ask(p<<1|1,ql,qr));
return res;
}
}seg;
int main(){
scanf("%d%d%d",&n,&k,&m);
seg.init(2*n);
for(int i=1;i<=m;++i){
scanf("%d%d",&x,&y);
pos=y+abs(x-k);
//printf("p:%d\n",pos);
if(cell.count(1ll*x*N+y)){//
cell.erase(1ll*x*N+y);
num[pos]--;
if(num[pos]==0){
now.erase(pos);
}
seg.chg(1,1,pos,-1);
}
else{
cell.insert(1ll*x*N+y);
num[pos]++;
if(num[pos]==1){
now.insert(pos);
}
seg.chg(1,1,pos,1);
}
if(now.empty())puts("0");
else printf("%d\n",max(0,seg.ask(1,1,*now.rbegin())-n));
}
return 0;
}
