Submission #16924046

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; using namespace atcoder;
void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N, K, X[201010];
int Q;
//---------------------------------------------------------------------------------------------------
int toRight[201010], toLeft[201010];
int toR[19][201010], toL[19][201010];
int totR[19][201010], totL[19][201010];
//---------------------------------------------------------------------------------------------------
int getTot(int L, int R) {
	int res = 1;
	int cu = L;
	rrep(p, 18, 0) {
		if (toR[p][cu] <= R) {
			res += 1 << p;
			cu = toR[p][cu];
		}
	}
	return res;
}
int getRight(int L, int R) {
	int cnt = getTot(L, R);

	ll tot = R; cnt--;
	int cu = R;
	rep(p, 0, 19) if (cnt & (1 << p)) {
		tot += totL[p][cu];
		cu = toL[p][cu];
	}

	return tot;
}
int getLeft(int L, int R) {
	int cnt = getTot(L, R);

	ll tot = L; cnt--;
	int cu = L;
	rep(p, 0, 19) if (cnt & (1 << p)) {
		tot += totR[p][cu];
		cu = toR[p][cu];
	}

	return tot;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	rep(i, 0, N) cin >> X[i];
	cin >> Q;

	rep(i, 0, N) toRight[i] = lower_bound(X, X + N, X[i] + K) - X;
	rep(i, 0, N) {
		int id = upper_bound(X, X + N, X[i] - K) - X;
		toLeft[i] = id - 1;
	}

	rep(p, 0, 19) toR[p][N] = N;
	rep(i, 0, N) toR[0][i] = toRight[i];
	rep(p, 1, 19) rep(i, 0, N) toR[p][i] = toR[p - 1][toR[p - 1][i]];

	rep(i, 0, N) totR[0][i] = toR[0][i];
	rep(p, 1, 19) rep(i, 0, N) totR[p][i] = totR[p - 1][i] + totR[p - 1][toR[p - 1][i]];

	rep(i, 0, N) toL[0][i] = toLeft[i];
	rep(p, 1, 19) rep(i, 0, N) {
		if (toL[p - 1][i] < 0) toL[p][i] = -1;
		else toL[p][i] = toL[p - 1][toL[p - 1][i]];
	}

	rep(i, 0, N) totL[0][i] = toL[0][i];
	rep(p, 1, 19) rep(i, 0, N) {
		if (toL[p - 1][i] < 0) totL[p][i] = totL[p - 1][i];
		else totL[p][i] = totL[p - 1][i] + totL[p - 1][toL[p - 1][i]];
	}

	rep(q, 0, Q) {
		int L, R; cin >> L >> R;
		L--; R--;
		ll ans = getRight(L, R) - getLeft(L, R) + getTot(L, R);
		printf("%lld\n", ans);
	}

}

Submission Info

Judge Result