Educational Codeforces Round 90 (Rated for Div. 2) - G. Pawns

题意：

一个 $n \times n$n×n 的棋盘上会有 $m$m 次变化，每次变化都会在某个空的位置上出现一个兵 或者 移去存在棋盘上的某个兵；
一个兵处于坐标 $(x,y)$(x,y) 可以移动到 $(x,y+1)$(x,y+1) , $(x-1,y+1)$(x−1,y+1) 或 $(x+1,y+1)$(x+1,y+1)，前面是列，后面是行；
有一个特殊列 $k$k，每次变化，你都要计算把所有的兵移动到第 $k$k 列（不可以重叠），需要在棋盘上第 $n$n 行之后额外添加的最少行数；

分析：

根据题意，不论列坐标怎么移动，行坐标每次 $+1$+1 ，所以在一个兵最少移动次数 到达第 $k$k 列之后，如果当前坐标已经有兵了，那么就不断递增行坐标直到找到第一个空的位置（行不够了就加），则先把所有的兵移动到离它最近的第 $k$k 列的位置，并统计第 $k$k 列上所有位置的兵的个数，那么需要考虑的就是第 $k$k 列两个相邻有兵的位置之间的溢满情况以及对后续的影响；
如果只求一次那么不难想，第 $k$k 列从前到后遍历一遍维护溢满情况就可以了，但是这里每次变化都要求一遍，所以得需要一个维护方法：
我们知道，假设 $(k,y)$(k,y) 有兵且它对答案有影响，要么是前面溢满了得跳过它，否则它就是答案的起点；
所以我们把第 $k$k 列每个点的初始值设置为它的行坐标$-1$−1 ，例如 $(k,i)$(k,i) 的初始值是 $i-1$i−1 ，每次添加一个兵，若离它最近的第 $k$k 列坐标是 $(k,y)$(k,y) ，则把 $[1,k]$[1,k] 区间全部加上 $1$1 即可，明显可以用线段树维护。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define st first
#define nd second
#define P pair<int,int>
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define frep(i,a,b) for(int i=a;i>=b;i--)
const int N = 2E5+10; 

int n,k,m;
int w[N<<3];
int add[N<<3];
int cnt[N<<1];

void build(int l,int r,int rt){
	if(l==r){
		w[rt]=l-1;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	w[rt]=max(w[ls],w[rs]);
}

void pushdown(int rt){
	if(add[rt]==0) return;
	w[ls]+=add[rt];
	w[rs]+=add[rt];
	add[ls]+=add[rt];
	add[rs]+=add[rt];
	add[rt]=0;
	return;
}

void upd(int l,int r,int rt,int L,int R,int x){
    if(L<=l&&r<=R){
    	  w[rt]+=x;
    	add[rt]+=x;
    	return;
	}
	pushdown(rt);
	int mid=(l+r)>>1;
	if(L<=mid) upd(l,mid,ls,L,R,x);
	if(R>mid) upd(mid+1,r,rs,L,R,x);
	w[rt]=max(w[ls],w[rs]);	
}

int qry(int l,int r,int rt,int L,int R)
{
	if(L<=l&&r<=R) return w[rt];
	pushdown(rt);
	int mid=(l+r)>>1;
	int ANS=0;
	if(L<=mid) ANS=max(ANS,qry(l,mid,ls,L,R));
	if(R>mid) ANS=max(ANS,qry(mid+1,r,rs,L,R));
	return ANS;
}

int main()
{
	//freopen("1.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>k>>m;
	build(1,n+n,1);
	set<P>s;
	set<int>D;
	
	while(m--)
	{
		int x,y; cin>>x>>y;
		int pos=y+(int)abs(x-k);
		P p=P(x,y);
		if(s.count(p))
		{
			--cnt[pos];
			if(cnt[pos]==0) D.erase(pos);
			upd(1,n+n,1,1,pos,-1);
			s.erase(p);
		}
		else
		{
			++cnt[pos];
			if(cnt[pos]==1) D.insert(pos);
			upd(1,n+n,1,1,pos,1);
			s.insert(p);
		}
		if(D.empty()) cout<<0;
	    else cout<<max(0,qry(1,n+n,1,1,*D.rbegin())-n);
	    cout<<endl;
	}	
}