自动搬运

查看原文

来自洛谷，原作者为

	UnyieldingTrilobite 直到世界 只剩下闪烁的黑白

搬运于2025-08-24 22:07:10，当前版本为作者最后更新于2022-03-11 10:36:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这题啊……真的是无话可说了，做完浑身舒畅的那种。

我们先不考虑 corner case。

首先肯定是按套路假设一轮过完之后起点移动的向量是 $(dx,dy)$。

我们考虑每一次的到达的点其实是很有规律的，对应点坐标之间会恰好差一个 $(dx,dy)$。那我们不难想到给它取模一下（不妨 $dx>0$）。

具体来说，我们用 $(x,y,t)$ 来表示 $(x+t\times dx,y+t\times dy)$，同时要求 $x\in[0,dx)$。

这样的话，我们如果先暴力走一轮，那么对于一个走到的点 $(x,y,r)$（注意这里 $r$ 不一定等于 $0$，因为有可能走到 $dx$ 外面去），我们实际上能走到的点是 $(x,y,r),(x,y,r+1),\cdots,(x,y,r+k-1)$，这本身是一个很好看的区间形式。注意起始点要特判一下，不过这不重要。

那么我们考虑正方形的四个顶点。我们会发现，如果对于一个 $r$，这四个点的前两维坐标都是合法的，那么就会产生 $1$ 的贡献。那么我们不妨换它一下，枚举四个顶点的前两维坐标（实际上只会有线性个这样的坐标，因为它们一定都在第一轮中出现过），然后考虑它们出现的位置（一定分别是若干个区间的并，这个开始扫一遍就可以搞定）的交，这玩意就很好处理了，来挑战这道题的人想必都会。注意有可能比如枚举左下角的时候发现另外三个点里有点的 $x$ 坐标达到了 $dx$，那没有关系，还是先转换成我们的标准坐标形式，对搞出来的范围平移一下就好了。

接下来是一些 corner case。

1. $dx<0$

把所有 E 和 W 交换就好了。

2. $dx=0,dy\not=0$

把 $dx$ 和 $dy$ 交换一下就好了。有可能需要用上面第一种情况额外处理一下。

3. $dx=dy=0$

每一轮都一样，走一轮就好了。可以把 $dx$ 手动改成充分大来回避其他问题。

代码（采用的区间是左闭右开的）：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>itv;
int dx,dy;
map<itv,set<itv>>cnt;
void init(){
	int n,k;
	string s;
	cin>>n>>k>>s;
	auto op=[](int&x,int&y,char c){
		switch(c){
			case 'E':++x;break;
			case 'N':++y;break;
			case 'W':--x;break;
			case 'S':--y;break;
		}
	};
	for(char c:s)op(dx,dy,c);
	auto trans=[&s](vector<pair<char,char>>trs){
		for(char&c:s)
			for(auto[c1,c2]:trs)
				if(c==c1)c=c2;
				else if(c==c2)c=c1;
	};
	if(!dx){
		swap(dx,dy),trans({{'E','N'},{'W','S'}});
		if(!dx)dx=250637,k=1;
	}
	if(dx<0)dx=-dx,trans({{'E','W'}});
	auto ins=[](itv pos,itv val){
		auto&st=cnt[pos];
		auto itl=st.lower_bound({val.first,INT_MIN});
		if(itl!=st.begin()&&prev(itl)->second>=val.first)--itl;
		auto itr=st.upper_bound({val.second,INT_MAX});
		if(itl==itr)st.insert(val);
		else{
			int l=min(itl->first,val.first),r=max(prev(itr)->second,val.second);
			st.erase(itl,itr),st.emplace(l,r);
		}
	};
	ins({0,0},{0,1});
	for(int x=0,y=0;char c:s){
		op(x,y,c);
		int dt=x/dx,px=x-dt*dx,py=y-dt*dy;
		if(px<0)px+=dx,py+=dy,--dt;
		ins({px,py},{dt,k+dt});
	}
}
signed main(){
	long long ans=0;
	auto atval=[](int x,int y){
		vector<itv>ret;
		int dt=0;
		if(x==dx)x-=dx,y-=dy,dt=1;
		if(auto it=cnt.find({x,y});it!=cnt.end()){
			ret.reserve(it->second.size());
			copy(it->second.begin(),it->second.end(),back_inserter(ret));
			for(auto&[l,r]:ret)l-=dt,r-=dt;
		}
		return ret;
	};
	auto merge=[](auto x,auto y){
		vector<itv>ret;
		for(auto pos=y.begin();auto[l,r]:x)
			while(pos!=y.end()){
				while(pos!=y.end()&&pos->second<=l)++pos;
				if(pos==y.end()||pos->first>=r)break;
				ret.emplace_back(max(l,pos->first),min(r,pos->second));
				if(pos->second>=r)break;
				else ++pos;
			}
		return ret;
	};
	for(init();auto[pos,iv]:cnt){
		auto[x,y]=pos;
		for(auto[l,r]:merge(merge(atval(x,y),atval(x+1,y+1)),merge(atval(x+1,y),atval(x,y+1))))
			ans+=r-l;
	}
	return cout<<ans<<endl,0;
}