AtCoder ACL Contest 1 : D - Keep Distances

これすんなり思い浮かばなかった。
https://atcoder.jp/contests/acl1/tasks/acl1_d

問題

1次元座標上にN個の点が並んでおり、点iの座標X[i]が与えられる。
また、正整数Kが指定されている。
以下のクエリに答えよ。

• 点の区間[L,R]が指定される。区間内の点において、互いの距離がK以上となるようにいくつかを選択したい。最大数を選択できる点の集合は何通りか。

解法

f(v,p) := 点vから初めて、右側距離K以上の最寄りの点を選ぶ作業をp回行ったときの点の番号
g(v,p) := 点vから初めて、左側距離K以上の最寄りの点を選ぶ作業をp回行ったときの点の番号
とする。f(v,2p)=f(f(v,p),p)なので、事前にダブリングしておけばf(v,p)はlog(p)で求められる。gについても同様。

各クエリにおいて、f(L,p)がR以下となる最大のpを求めれば、まず選択できる最大数は求められる。
その値をqとしよう。g(R,q)がL以上になるのは自明である。
あとは、g(R,q-x)-f(L,x)をx=0～qの範囲で求められれば良い。

とすると、解はG(R,p)-F(v,p)である。
F,Gもダブリングで高速に計算できるので、各クエリO(logN)で処理できる。

int N,K;
ll X[202020];
int Q;
int L,R;
int le[21][202020];
int ri[21][202020];
ll LS[21][202020];
ll RS[21][202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>X[i+1];
	X[0]=-1LL<<60;
	X[N+1]=1LL<<60;
	for(i=1;i<=N;i++) {
		ri[0][i]=lower_bound(X,X+N+2,X[i]+K)-X;
		le[0][i]=lower_bound(X,X+N+2,X[i]-K+1)-X-1;
		LS[0][i]=le[0][i];
		RS[0][i]=ri[0][i];
	}
	
	le[0][0]=0;
	ri[0][N+1]=N+1;
	FOR(j,20) {
		for(i=0;i<=N+1;i++) {
			le[j+1][i]=le[j][le[j][i]];
			ri[j+1][i]=ri[j][ri[j][i]];
			LS[j+1][i]=LS[j][i]+LS[j][le[j][i]];
			RS[j+1][i]=RS[j][i]+RS[j][ri[j][i]];
		}
	}
	
	
	cin>>Q;
	FOR(i,Q) {
		cin>>L>>R;
		ll dif=R-L+1;
		x=L,y=R;
		for(j=19;j>=0;j--) {
			if(ri[j][x]<=R) {
				dif+=LS[j][y]-RS[j][x]+(1<<j);
				x=ri[j][x];
				y=le[j][y];
			}
		}
		cout<<dif<<endl;
	}
	
	
	
}

まとめ

本番累積和取ることに考えが至らなかった。