yukicoder : No.1170 Never Want to Walk

いろいろ解法がありそうね。
https://yukicoder.me/problems/no/1170

問題

1次元座標上でN個の点の座標X[i]が昇順で与えられる。
最短距離がA以上B以下の2点間に辺を張ったグラフを考えたとき、各点が属する連結成分のサイズを求めよ。

解法

頂点uに対して、X[u]+A≦X[v]≦X[u]+Bである頂点vすべてに辺を張ることになる。
X[u]+A≦X[v]≦X[u]+Bとなるvの範囲が[p,q]とする。このp,qは二分探索で求められる。

問題は辺を張る処理。区間に辺を張る処理としてSegTreeの考えを応用したテクもあるが、以下では別のテクを使う。
uとp≦v≦qとなる全vに対し辺を張って連結する処理は、以下の3通りの辺に分解できる。

• u-p間
• u-q間
• p≦v＜qとなるvに対し、v-(v+1)間

よって、上2つは普通に辺を張って、3つ目は累積和の要領で「右隣の頂点に辺を1本以上張るか？」を求めておけばよい。

int N,A,B;
int X[202020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;

int add[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	FOR(i,N) cin>>X[i];
	
	FOR(i,N) {
		x=lower_bound(X+i+1,X+N,X[i]+A)-X;
		y=lower_bound(X+i+1,X+N,X[i]+B+1)-X-1;
		if(y>=x) {
			uf(i,x);
			uf(i,y);
			add[x]++;
			add[y]--;
		}
	}
	
	FOR(i,N) {
		if(i) add[i]+=add[i-1];
		if(add[i]) uf(i,i+1);
	}
	FOR(i,N) cout<<uf.count(i)<<endl;
	
}

まとめ

歩きたくないけど電車の遠出は苦にならないタイプなのね。