P5102 [JOI 2016 Final] 领地 / Territory 题解

link 本题为原T3（致敬传奇gjoj T3 放黑）

题意

小 L 在二维平面从 $(0,0)$ 出发，每天走长度为 $n$ 的路径 $s$（E,N,W,S 表示方向），每天起点是前一天终点。旅行 $k$ 天。

定义：

• 好的点：至少被经过一次的点。

• 完美的点：$(x,y)$ 满足 $(x,y), (x,y+1), (x+1,y), (x+1,y+1)$ 都是好的点。

求完美点的数量。

$1\leq N\leq 10^5,1\leq K\leq 10^9$。

---

做法

使用了这篇题解的做法（gjoj 上给的还是太抽象了）。

首先我们要记录的肯定有每一轮对于前一轮的偏移量 $(dx,dy)$，这个等价于完整的一轮后到达的终点 $(x,y)$。

考虑我们完整的模拟一遍。

然后我们考虑在 $k$ 步后出现的点中，相差 $(dx,dy)$ 的点归为一个集合，这样子就会有若干个集合。

给每一个集合一个索引，先不考虑这个索引是什么。

然后我们针对某个点 $p$，通过这个点的坐标算出其他三个点的坐标。

以这四个点，通过某种神秘方法找到他们的集合，令这四个集合（$p$ 点、右侧、上侧、右上）为 $S,U,R,UR$，再看看集合内有多少个位置 $(i,j)$ 满足 $(i+j)\in S$ 且 $(i+1,j)\in R$ 且 $(i,j+1)\in U$ 且 $(i+1,j+1)\in UR$。

事实上这种做法中，集合就像是直线 $kx+b$ 上的点。给你一个东西来访问四条直线，再找到有交集的点位来统计答案。

比如说以下这个例子：

考虑标橙的点为 $p$，找到 $p$ 的右、上、右上三个点，得到 紫线、红线、绿线、黄线四个集合。

查看四个集合内是否有符合要求的点位：可以看到 $(1,1)$ 和 $(2,3)$ 都符合，这样就完成了答案的统计。

---

可以发现，这样的做法中存在几个问题：

1. 单个集合存储 $k$ 步后点位开销过大

2. 索引怎么算

3. 怎么能快速统计符合要求的点位

首先我们考虑怎么样能使点位开销变小。

对于第一轮出现的点 $(x_i,y_i)$，在经过 $k$ 次操作后会变成 $(x_i+k\cdot dx,y_i+k\cdot dy)$。

可以发现，这 $k$ 次操作生成的点都在一条直线上，并且他们是连续的。

那么我们就考虑不直接维护一个集合内究竟有什么点，而是维护这些点相较于 $(x_0,y_0)$ 的偏移次数，方便说是。

假设 $x_i=x_0+l\cdot dx,\;y_i=y_0+l\cdot dy$，那么 $k$ 次操作的区间范围就是 $[l,l+k-1]$。

那么就可以使用连续区间来表示集合了。很显然发现这样操作对于集合而言是不漏的。

考虑重复的问题。

假如在第一轮中出现了 $1$ 和 $3$，$k=3$，那么直接算的区间是 $[1,3]$ 和 $[3,5]$。

这是有重复的。不过我们可以从左到右合并区间即可。

---

然后我们来同时考虑第二和第三点。

在第一点中，我们使用了若干区间来表示一个集合。这导致四个集合看起来就像是这个东西：

因为集合已经没有具体的坐标了，这就是说，这四个集合的 $(x_0,y_0)$ 肯定也得是一个正方形。只有在这种情况下，四个集合的同一个值才能对应上。

然后直接扫一遍求交集就好了，来挑战这道题的人想必都会。

对于 $(x_0,y_0)$，仅此而已。

那索引呢？要想从“点”容易的访问到集合，考虑到还得维护每个集合的 $(x_0,y_0)$，不如就让索引是 $(x_0,y_0)$ 罢！

有一个能从“点”到索引的关系：考虑点 $(i,j)$ ，令 $s=\min(\lfloor \frac{i}{dx}\rfloor,\lfloor \frac{j}{dy}\rfloor )$，那么 $x_0=i-s\cdot dx,\;y_0=j-s\cdot dy$。（不考虑负数）

那这样子的索引是有部分连续性的。因此可以比较方便的访问其他集合：

显然，一个集合内，具体是什么点访问到这个集合是不重要的，因此直接考虑使用索引。

以 $(x_0,y_0)$ 来访问 $S$，这个是可以确定的。

以 $(x_0+1,y_0)$ 来访问 $R$？如果说 $s'=\min(\lfloor \frac{x_0+1}{dx}\rfloor,\lfloor \frac{y_0}{dy}\rfloor)\neq 0$，那么这就说明了，$R$ 是从更小的 $(x_0',y_0')$ 开始的。

这就需要对 $R$ 进行一个偏移。如图所示：

其他两个同理。

可能有人会想，为什么要这么麻烦，直接使用这个集合最小的点不就好了？

显然这样是不对的。我要使用 D 就不对了。

然后显然对整幅图做 左右/上下翻转 和 平移 就可以规避负数的问题。

那么这道题逻辑层面的做法就是这样。

细节

下面主要讲一下实现上的细节：

1. 对 $dx=dy=0$ 做一个特判

2. 对 dx=0 \or dy=0 也需要做一个特判。由于求 $s$ 的过程需要除法运算。

   考虑这种情况长什么样（以 $dx=0$ 举例）：

   

   $dx=0$ ，那我们就不用刻意考虑 $x$ 了。直接以 $x_0=x,y_0=y \bmod dy$ 建集合即可。$dy=0$ 同理。

3. 对集合进行偏移时，可能会出现集合内区间 $l$ 或 $r$ 小于 $0$ 的情况。如果 $l<0,r\geq 0$，就 $l\leftarrow 0$。如果 $l,r<0$，就不要了。

4. 记得把出发点处理！

代码

// #define DEBG 1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn=1e5+35;
const ll inf=1e18;

int f[150][2];
void initf(){
	f['E'][0]=1;f['E'][1]=0;
	f['N'][0]=0;f['N'][1]=1;
	f['W'][0]=-1;f['W'][1]=0;
	f['S'][0]=0;f['S'][1]=-1;
}

inline PII operator * (int k,PII x){
	return {x.first*k,x.second*k};
}
inline void operator -= (PII &x,PII y){
	x.first-=y.first;x.second-=y.second;
}




int n,k;
char s[maxn];
void input(){
	n=read();k=read();
	read(s+1);
}

int dx,dy;
void calc_delta(){
	int x=0,y=0;
	for(int i=1;i<=n;++i){
		char way=s[i];
		x+=f[way][0];
		y+=f[way][1];
	}
	if(x<0){
		for(int i=1;i<=n;++i){
			if(s[i]=='E') s[i]='W';
			else if(s[i]=='W') s[i]='E';
		}
		x=-x;
	}
	if(y<0){
		for(int i=1;i<=n;++i){
			if(s[i]=='N') s[i]='S';
			else if(s[i]=='S') s[i]='N';
		}
		y=-y;
	}
    //对dx的方向做出调整，即翻转，规避负数
	dx=x;dy=y;
}

int xshift,yshift;
void calc_nagative_shift(){
	int x=0,y=0;
	for(int i=1;i<=n;++i){
		char way=s[i];
		x+=f[way][0];
		y+=f[way][1];
		if(x<0) xshift=max(xshift,-x);
		if(y<0) yshift=max(yshift,-y);
	}
    //计算偏移量，规避负数
}



//定义一条直线：表示为初始点为 (x0,y0) 斜率为 (dx,dy) 的线
//(x0,y0) 必须模到底
map<PII,vector<ll> > line;//使用偏移次数来保存每一直线上的每一点
void go1(){
	int x=xshift,y=yshift;
	ll g=min(x/dx,y/dy);
	PII sp={x-g*dx,y-g*dy};
	line[sp].emplace_back(g);

	for(int i=1;i<=n;++i){
		char way=s[i];
		x+=f[way][0];
		y+=f[way][1];
		
		ll g=min(x/dx,y/dy);
		PII sp={x-g*dx,y-g*dy};
		//计算x0,y0，减去g个dx和g个dy
		line[sp].emplace_back(g);
	}
}


struct Seg{
	ll l,r;
	Seg(){}
	Seg(ll l,ll r):l(l),r(r){}
};
map<PII,vector<Seg> > lineseg;//将k转换为若干区间
void to_seg(){
	for(auto it=line.begin();it!=line.end();++it){
		ll sx=it->first.first,sy=it->first.second;
		PII sp={sx,sy};

		sort(it->second.begin(),it->second.end());
		auto end=unique(it->second.begin(),it->second.end());
		it->second.erase(end,it->second.end());
        //因为一个点可能访问多次，因此要去重

		ll l=-inf,r=-inf;
		for(auto p: line[sp]){
			if(p==r+1) r=p;
			else{
				if(r!=-inf) lineseg[sp].push_back(Seg(l,r));
				l=p,r=p;
			}
		}//连续的点要合并成一个区间
		lineseg[sp].push_back(Seg(l,r));
	}
}


vector<Seg> segtok;//这是一个临时变量
bool del[maxn];
void gok(){//延伸到k步
	for(auto it=lineseg.begin();it!=lineseg.end();++it){
		ll sx=it->first.first,sy=it->first.second;
		PII sp={sx,sy};
		auto segv=&(it->second);

		for(auto seg: *segv){
			segtok.push_back({seg.l,seg.r+k-1});
		}
		memset(del,0,sizeof(bool)*(segtok.size()+5));
		for(int i=0;i<segtok.size()-1;++i){
			if(segtok[i].r>=segtok[i+1].l-1){
				del[i]=1;
				segtok[i+1]=Seg(segtok[i].l,segtok[i+1].r);
			}
		}//重叠的区间需要合并
		segv->clear();
		for(int i=0;i<segtok.size();++i){
			if(!del[i]){
				segv->push_back(segtok[i]);
			}
		}
		segtok.clear();
        //这里直接修改了lineseg
	}
}


// #define O 0
#define UR 3
#define R 1
#define U 2

PII sp[4];
ll sh[4];
void calc_4dot(){//给出第一个索引，计算其他三个索引
	ll sx=sp[0].first,sy=sp[0].second;
	sh[1]=sh[2]=sh[3]=inf;

	sp[R]={sx+1,sy};    if(dx) sh[R]=(sx+1)/dx;   if(dy) sh[R]=min(sh[R],sy/dy);
	sp[U]={sx,sy+1};    if(dx) sh[U]=sx/dx;       if(dy) sh[U]=min(sh[U],(sy+1)/dy);
	sp[UR]={sx+1,sy+1}; if(dx) sh[UR]=(sx+1)/dx;  if(dy) sh[UR]=min(sh[UR],(sy+1)/dy);

	sp[R]-=sh[R]*PII({dx,dy}); sp[U]-=sh[U]*PII({dx,dy}); sp[UR]-=sh[UR]*PII({dx,dy});
}


vector<Seg> segv[4];
void edit_segv(){
	for(int i=0;i<4;++i){
		segv[i].clear();
		PII stp=sp[i];
		if(!lineseg.count(stp)) continue;
        //这里，偏移集合
		for(auto seg: lineseg[stp]){
			ll l=seg.l-sh[i],r=seg.r-sh[i];
			if(r<0) continue; //嘟嘟3
			l=max(l,0ll);
			segv[i].push_back({l,r});
		}
	}
}

ll ans;
void add_ans(){//对4个集合求交集了
	int i[4]={0,0,0,0};
	while(1){
		for(int j=0;j<4;++j){
			if(i[j]>=segv[j].size()) return;
		}

		ll mxst=-inf,mnen=inf;
		for(int j=0;j<4;++j){
			mxst=max(mxst,segv[j][i[j]].l);
			mnen=min(mnen,segv[j][i[j]].r);
		}
		if(mnen<mxst){
			for(int j=0;j<4;++j){
				while(i[j]<segv[j].size()&&segv[j][i[j]].r<mxst) ++i[j];
			}
		}
		else{
			ans+=mnen-mxst+1;
			// cout<<"upd: "<<sp[0].first<<" "<<sp[0].second<<" "<<mxst<<" "<<mnen<<" "<<endl;
			for(int j=0;j<4;++j){
				if(segv[j][i[j]].r==mnen) ++i[j];
			}
		}
	}
}

void solve(){
	for(auto it=lineseg.begin();it!=lineseg.end();++it){
		ll sx=it->first.first,sy=it->first.second;
		sp[0]={sx,sy}; sh[0]=0;
        //直接枚举每一个集合。我们知道它的索引，所以直接使用索引把其他3个的索引给获取到
        //获取到集合，再做个偏移，就可以求交集了
		
		calc_4dot();
		edit_segv();
		add_ans();
	}
}

namespace Delta0{
	set<PII> vis;
	void solve(){
		int x=0,y=0;
		for(int i=1;i<=n;++i){
			char way=s[i];
			x+=f[way][0];
			y+=f[way][1];
			vis.insert({x,y});
		}
		for(auto p: vis){
			PII now=p,r={p.first+1,p.second},u={p.first,p.second+1},ur={p.first+1,p.second+1};
			if(vis.count(r)&&vis.count(u)&&vis.count(ur)) ++ans;
		}
	}
}

namespace Delta1{
	void go1(){
		int x=xshift,y=yshift;
		if(dx==0) line[{x,y%dy}].push_back(y/dy);
		if(dy==0) line[{x%dx,y}].push_back(x/dx);
		for(int i=1;i<=n;++i){
			char way=s[i];
			x+=f[way][0];
			y+=f[way][1];
			if(dx==0) line[{x,y%dy}].push_back(y/dy);
			if(dy==0) line[{x%dx,y}].push_back(x/dx);
		}
	}
}

int main(){
	initf();
	input();
	calc_delta();
	if(dx==0&&dy==0){
		Delta0::solve();
	}
	else if(dx==0||dy==0){
		calc_nagative_shift();
		Delta1::go1();
		to_seg();
		gok();
		solve();
	}
	else{
		calc_nagative_shift();
		go1();
		to_seg();
		gok();
		solve();
	}
	printf("%lld",ans);
	return 0;
}

复杂度分析

首先计算 $dx,dy$ 和偏移的复杂度肯定是 $O(n)$ 的。

由于每个点都只属于一个集合内，因此 go1 的复杂度也是 $O(n)$ 的。（可能有 $\log$）

每一个点对应了一个区间，将每一个区间延伸至 $k$ 步，gok $O(n)$。

重点是计算答案时：

显然一个集合只能被他自己、他左边、他下面、他左下四个索引点访问到。因此如果有集合需要偏移，总复杂度为 $O(4n)$。

然后计算交集是直接把 4 个集合的所有区间给便利，同样是 $O(4n)$。

其实我可以用 unordered_map<PII,vector<Seg> > lineseg 的但是可能是 pair 没有哈希也有可能是我把这事忘了导致白白送出一个 $\log$。

总复杂度 $O(n\log^2 n)$