自动搬运

查看原文

来自洛谷，原作者为

	wrkwrkwrk ？

搬运于2025-08-24 23:11:23，当前版本为作者最后更新于2025-03-21 16:11:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们可以容易知道：若一个点在 $2 \times 2$ 的格子中，则不能被移除。

在确定以上条件的情况下，若一个点在两个上述格子之间，存在一条链按阶梯状递增，则也不能被移除。

容易证明上述为等价条件。且若一个格子不在 $2\times 2$ 方格中，且不能被移除，则至多在一个阶梯状中。

直接模拟上述过程即可。

这里使用 odt 维护阶梯。对每条平行于主对角线和副对角线分别维护。

一个点 $(x,y)$ 可以加入 $x+y,x+y-1$ 的副对角线和 $x-y$，$x-y-1$ 的主对角线。

考虑 odt 的内部顺序判断以方便，这里分别定义如下内容：

struct cmp1{
	bool operator()(node a,node b)const{
		auto p=a.first,q=b.first;
		return p.first==q.first?p.second<q.second:p.first>q.first; 
	}
};
struct cmp2{
	bool operator()(node a,node b)const{
		auto p=a.first,q=b.first;
		return p.first==q.first?p.second<q.second:p.first<q.first; 
	}
};

这样可以通过自定义比较函数的方式定义 odt。通过存储目前加入过的点的集合方便找到 +1 -1。

node 维护最前，后点，左，右侧是否封闭，当前是否不能被删除，当前是否是 $2 \times 2$ 格子中的点。在 $2 \times 2$ 格子中的点单独存储。

插入时注意判断前驱，后继是否相邻且是否是 $2 \times 2$ 格子中的点（距离是否等于1）。

标记点的时候注意判断本身是不是已经是不能被删除，两侧是否封闭。

清除标记判断左右两侧。注意指针不要指错。

删除点保留所在段左右侧的值。

如上都返回当前在阶梯状被认为不可删除的点的数量变化量。

剩下的直接判断，加入，标记，去除标记，删除即可。反正只会影响周边的点。

时间复杂度 $O((k+q)\log(k+q))$，常数巨大。

写的很长，7.1k，不清楚长度不超过 3k 的代码咋写的。

#include<bits/stdc++.h>
using namespace std;
struct node{
	pair<int,int>first,second;
	bool cntl,cntr,ue,uc;
};
struct cmp1{
	bool operator()(node a,node b)const{
		auto p=a.first,q=b.first;
		return p.first==q.first?p.second<q.second:p.first>q.first; 
	}
};
struct cmp2{
	bool operator()(node a,node b)const{
		auto p=a.first,q=b.first;
		return p.first==q.first?p.second<q.second:p.first<q.first; 
	}
};
int dis(pair<int,int>a,pair<int,int>b){
	return abs(a.first-b.first)+abs(a.second-b.second); 
}
template<class cmp>
struct odt{
	set<node,cmp>z;
	set<node,cmp>zc;
	int insert(pair<int,int>f){
		zc.insert({f});
		auto c=z.lower_bound({f,f,0,0,0,0});
		node nc={f,f,0,0,0,0};
		if(c!=z.begin()&&dis({prev(c)->second.first,prev(c)->second.second},f)==1){
			if(prev(c)->ue){
				nc.cntl=1;
			}else{
				nc.first=prev(c)->first;
				nc.cntl=prev(c)->cntl;
				z.erase(*prev(c));
			}
		}
		if(c!=z.end()&&dis({(c)->first.first,(c)->first.second},f)==1){
			if(c->ue){
				nc.cntr=1;
			}else{
				nc.second=c->second;
				nc.cntr=c->cntr;
				z.erase(*c);
			}
		}
		int res=0;
		if(nc.cntl&&nc.cntr){
			res=dis(nc.first,nc.second)+1;
			nc.ue=1;
		}
		z.insert(nc);
		return res;
	}
	int mark(pair<int,int>f){
		auto c=prev(z.upper_bound({f,f,0,0,0,0}));
		if(!c->ue){
			auto fc=*c;
			z.erase(fc);
			int res=0;
			z.insert({f,f,1,1,1,1}); 	
			if(fc.first!=f||fc.second!=f){
				if(fc.first!=f){
					auto w=prev(zc.lower_bound({f}))->first;
					auto zf=fc;
					zf.second=w;
					zf.cntr=1;
					if(zf.cntl){
						zf.ue=1;
						res+=dis(zf.first,zf.second)+1;
					}
					z.insert(zf);
				}
				if(fc.second!=f){
					auto w=next(zc.lower_bound({f}))->first;
					auto zf=fc;
					zf.first=w;
					zf.cntl=1;
					if(zf.cntr){
						zf.ue=1;
						res+=dis(zf.first,zf.second)+1;
					}
					z.insert(zf);
				}
			}
			return res;	
		}else if(!c->uc){
			auto fc=*c;
			z.erase(fc);
			z.insert({f,f,1,1,1,1});
			if(fc.first!=f){
				auto w=prev(zc.lower_bound({f}))->first;
				auto zf=fc;
				zf.second=w;
				z.insert(zf);
			}
			if(fc.second!=f){
				auto w=next(zc.lower_bound({f}))->first;
				auto zf=fc;
				zf.first=w;
				z.insert(zf);
			}
			return -1;
		}else{
			return 0;
		} 
		
	}
	int clearmark(pair<int,int>f){
		auto c=prev(z.upper_bound({f,f,0,0,0,0}));
		int res=0;
		node x={f,f,0,0,0,0};
		if(c!=z.begin()&&dis(prev(c)->second,f)==1){
			if(!prev(c)->uc){
				if(prev(c)->ue){
					res-=dis(prev(c)->first,prev(c)->second)+1;
				}
				x.first=prev(c)->first;
				x.cntl=prev(c)->cntl;
				z.erase(prev(c));
			}else{
				x.cntl=1;
			}
		}
		if(next(c)!=z.end()&&dis(next(c)->first,f)==1){
			if(!next(c)->uc){
					
				if(next(c)->ue)res-=dis(next(c)->first,next(c)->second)+1;
				x.second=next(c)->second;
				x.cntr=next(c)->cntr;
				z.erase(next(c)); 
			}else{
				x.cntr=1;
			}
		}
		z.erase(c);
		if(x.cntl&&x.cntr){
			x.ue=1;
			res+=dis(x.first,x.second)+1;
		}
		z.insert(x);
		return res;
	}
	int erase(pair<int,int>f){
		auto c=prev(z.upper_bound({f,f,0,0,0,0}));
		auto fc=*c;
		z.erase(c);
		int res=0;
		if(fc.ue){
			res-=dis(fc.first,fc.second)+1;
		}
		if(fc.first!=f){
			node x={};
			x.first=fc.first;
			x.second=prev(zc.lower_bound({f}))->first;
			x.cntl=fc.cntl;
			x.cntr=x.ue=x.uc=0;
			z.insert(x);
		}
		if(fc.second!=f){
			node x={};
			x.first=zc.upper_bound({f})->first;
			x.second=fc.second;
			x.cntl=0;
			x.cntr=fc.cntr;
			x.ue=x.uc=0;
			z.insert(x);
		}
		return res;
		
	}
	size_t size(){
		return z.size();
	}
};
template<class type,int l,int r>
struct pc_array{
	type w[r-l+1];
	type& operator[](int pos){
		return w[pos-l];
	}
};
pc_array<odt<cmp1>,0,400005>cl;
pc_array<odt<cmp2>,-200005,200005>cr;
struct has{
	unsigned long long operator()(pair<int,int>f)const{
		return (unsigned long long)f.first<<30|f.second;
	}
};
unordered_set<pair<int,int>,has>ff,fz;
int zc[5]; 
#define tot zc[0]
#define hap zc[1]
void insert1(int x,pair<int,int>y){
	hap=hap+cl[x].insert(y);
}
void insert2(int x,pair<int,int>y){
	hap=hap+cr[x].insert(y);
}
void mark1(int x,pair<int,int>y){
	hap=hap+cl[x].mark(y);
}
void mark2(int x,pair<int,int>y){
	hap=hap+cr[x].mark(y);
}
void clearmark1(int x,pair<int,int>y){
	hap=hap+cl[x].clearmark(y);
} 
void clearmark2(int x,pair<int,int>y){
	hap=hap+cr[x].clearmark(y);
} 
void erase1(int x,pair<int,int>y){
	hap=hap+cl[x].erase(y);
}
void erase2(int x,pair<int,int>y){
	hap=hap+cr[x].erase(y);
}
void insert(pair<int,int>wc){
	if(ff.find(wc)==ff.end()){
		ff.insert(wc);
		tot=tot+1;
		insert1(wc.first+wc.second-1,wc);
		insert1(wc.first+wc.second,wc);
		insert2(wc.first-wc.second-1,wc);
		insert2(wc.first-wc.second,wc);
	}
}
void mark(pair<int,int>wc){
	if(fz.find(wc)==fz.end()){
		mark1(wc.first+wc.second-1,wc);
		mark1(wc.first+wc.second,wc);
		mark2(wc.first-wc.second-1,wc);
		mark2(wc.first-wc.second,wc);
		fz.insert(wc);
	}
}
void clearmark(pair<int,int>wc){
	if(fz.find(wc)!=fz.end()){
		clearmark1(wc.first+wc.second-1,wc);
		clearmark1(wc.first+wc.second,wc);
		clearmark2(wc.first-wc.second-1,wc);
		clearmark2(wc.first-wc.second,wc);
		fz.erase(wc);
	}
}
void erase(pair<int,int>wc){
	if(ff.find(wc)!=ff.end()){
		tot=tot-1;
		erase1(wc.first+wc.second-1,wc);
		erase1(wc.first+wc.second,wc);
		erase2(wc.first-wc.second-1,wc);
		erase2(wc.first-wc.second,wc);
		ff.erase(wc);
	}
}
const vector<vector<pair<int,int>>>checkt={
	{{-1,-1},{-1,0},{0,-1},{0,0}},
	{{-1,0},{-1,1},{0,0},{0,1}},
	{{0,-1},{0,0},{1,-1},{1,0}},
	{{0,0},{0,1},{1,0},{1,1}},
};
const vector<pair<int,int>>rf={
	{-1,-1},{-1,0},{-1,1},
	{ 0,-1},	   { 0,1},
	{ 1,-1},{ 1,0},{ 1,1},

};
void adpoint(pair<int,int>x){
    insert(x);
    for(auto p:checkt){
	 	bool z=1;
	  	for(auto f:p){
	   		int xx=x.first+f.first,yy=x.second+f.second;
	  		if(ff.find({xx,yy})==ff.end()){
	   			z=0;
	   			break;
			}
		}
		if(z){
		   	for(auto f:p){
		   		int xx=x.first+f.first,yy=x.second+f.second;
		  		mark({xx,yy});
			}
		}
	}
}
void erasepoint(pair<int,int>x){
	clearmark(x);
	erase(x);
	for(auto f:rf){
		pair<int,int>nx={x.first+f.first,x.second+f.second};
		if(ff.find(nx)!=ff.end()){
			bool cf=0;
		    for(auto p:checkt){
			 	bool z=1;
			  	for(auto fc:p){
			   		int xx=nx.first+fc.first,yy=nx.second+fc.second;
			  		if(ff.find({xx,yy})==ff.end()){
			   			z=0;
			   			break;
					}
				}
				if(z){
					cf=1;
					break;
				}
			}
			if(!cf){
				clearmark(nx);
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,m,k,q;
	cin>>n>>m>>k>>q;
	map<pair<int,int>,int>tl;
	for(int i=1;i<=k;i++){
		int a,b;
		cin>>a>>b; 
		tl[{a,b}]=1;
		adpoint({a,b});
	}
    cout<<tot-hap-fz.size()<<'\n';
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y;
		if(!tl[{x,y}])adpoint({x,y});
		else erasepoint({x,y});
		tl[{x,y}]^=1;
		cout<<tot-hap-fz.size()<<'\n';
	}
	return 0;
}