自动搬运

查看原文

来自洛谷，原作者为

	周子衡 Shadow is the light!

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

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

以下是正文

对于每两块相邻的可用土地（不被蛇占据的土地，下称白点，反之为黑点）之间连一条边，形成图 $G$，显然题意就是求 $G$ 在横坐标 $[a_r,b_r]$，纵坐标 $[a_c,b_c]$ 范围内的连通块个数。

显然 $G$ 是一个平面图。根据平面图的欧拉公式，对于连通平面图 $G$，有 $|V|-|E|+|F|=1$，其中 $|V|,|E|,|F|$ 分别表示 $G$ 的点数、边数、划分平面数。进而推知：对于任意平面图 $G$，$|V|-|E|+|F|=G$ 的连通块数。考虑快速计算 $|V|,|E|,|F|$ 的值。

显然 $|V|,|E|$ 都很好计算：以 $|V|$ 为例，相当于计算 $[a_r,b_r][a_c,b_c]$ 内的白点个数，而白点个数较大，反面考虑，转化为计算该区域内黑点个数——由于黑点总数为 $O(m)$ 的，转化为简单二维数点问题，主席树即可解决。$|E|$ 包含两部分边：横边和竖边，分开考虑，每部分也是一个二维数点问题，亦可同上解决。

对于 $|F|$，原图的平面可能由两部分组成：一是若干 $1\times 1$ 的小正方形，这一部分相当于求四个点都是白点的数量，套用二维数点即可；另外要特别注意，如果矩形范围将蛇的范围完全包住并留有外隙，则 $|F|$ 额外加 $1$——令黑点的 $r,c$ 最大最小值为 $maxr,minr,maxc,minc$，则上述条件等价于 $a_r<minr$ 且 $b_r>maxr$ 且 $a_c<minc$ 且 $b_c>minc$。具体原理留给读者思考。

综上，我们得到了一个时间、空间复杂度均为 $O((r+c+m)\log c)$ 的做法，可以通过此题。**特别提醒：**特判 $m=0$，即 $S$ 为空的情况。

代码：

#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

int r=0,c=0,m=0,Q=0;

struct point
{
	int x,y;point(int xx=0,int yy=0):x(xx),y(yy){}
};bool operator<(point a,point b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}
bool operator==(point a,point b){return a.x==b.x&&a.y==b.y;}

vector<point> q[4];
void add_point(int x,int y)
{
	for(int i=0;i<4;i++)q[i].push_back(point(x,y));
	if(x<r){q[1].push_back(point(x+1,y)),q[3].push_back(point(x+1,y));}
	if(y<c){q[2].push_back(point(x,y+1)),q[3].push_back(point(x,y+1));}
	if(x<r&&y<c){q[3].push_back(point(x+1,y+1));}
}

struct PresidentTree
{
	struct nd
	{
		int lc,rc,sum;
	}t[7000000];int used;
	void build(int l,int r,int &k)
	{
		if(!k)k=++used;t[k].sum=0;if(l==r)return;
		int mid=(l+r)>>1;build(l,mid,t[k].lc),build(mid+1,r,t[k].rc);
	}
	int add(int pos,int val,int l,int r,int k)
	{
		int p=++used;t[p]=t[k];
		if(l==r){t[p].sum+=val;return p;}
		int mid=(l+r)>>1;if(pos<=mid){t[p].lc=add(pos,val,l,mid,t[k].lc);}else t[p].rc=add(pos,val,mid+1,r,t[k].rc);
		t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;return p;
	}
	int sum(int x,int y,int l,int r,int k)
	{
		if(l>y||r<x)return 0;
		if(x<=l&&r<=y)return t[k].sum;
		int mid=(l+r)>>1;return sum(x,y,l,mid,t[k].lc)+sum(x,y,mid+1,r,t[k].rc);
	}
}T[4];int rt[4][500000];

char S[500000];

int sum(int i,int ar,int ac,int br,int bc)
{
	if(ar>br||ac>bc)return 0;
	return T[i].sum(ac,bc,1,c,rt[i][br])-T[i].sum(ac,bc,1,c,rt[i][ar-1]);
}

int main()
{
	scanf("%d%d%d%d",&r,&c,&m,&Q);
	int sr=0,sc=0;scanf("%d%d",&sr,&sc);add_point(sr,sc);
	if(m)scanf("%s",S+1);
	int minr=sr,maxr=sr,minc=sc,maxc=sc;
	for(int i=1;i<=m;i++)
	{
		if(S[i]=='N')sr--;if(S[i]=='S')sr++;if(S[i]=='W')sc--;if(S[i]=='E')sc++;
		minr=min(minr,sr),maxr=max(maxr,sr),minc=min(minc,sc),maxc=max(maxc,sc);
		add_point(sr,sc);
	}
	//puts("");
	for(int i=0;i<4;i++)
	{
		sort(q[i].begin(),q[i].end());
		
		vector<point>::iterator new_end=unique(q[i].begin(),q[i].end());
		q[i].erase(new_end,q[i].end());
		//for(int j=0;j<q[i].size();j++)printf("%d %d\n",q[i][j].x,q[i][j].y);
		T[i].build(1,c,rt[i][0]);
		for(int j=1,p=-1;j<=r;j++)
		{
			rt[i][j]=rt[i][j-1];
			while(p+1<q[i].size()&&q[i][p+1].x==j)
			{
				p++;
				rt[i][j]=T[i].add(q[i][p].y,1,1,c,rt[i][j]);
			}
		}
		//puts("");
	}
	
	while(Q--)
	{
		int ar=0,ac=0,br=0,bc=0;scanf("%d%d%d%d",&ar,&ac,&br,&bc);long long R=br-ar+1,C=bc-ac+1;
		long long ans1=R*C-sum(0,ar,ac,br,bc);
		long long ans2=(R-1)*C-sum(1,ar+1,ac,br,bc);
		long long ans3=R*(C-1)-sum(2,ar,ac+1,br,bc);
		long long ans4=(R-1)*(C-1)-sum(3,ar+1,ac+1,br,bc);
		if(ar<minr&&br>maxr&&ac<minc&&bc>maxc)ans4++;
		//printf("%lld %lld %lld %lld\n",ans1,ans2,ans3,ans4);
		printf("%lld\n",ans1-ans2-ans3+ans4);
	}
	return 0;
}