徒歩圏内 [codeFlyer （bitFlyer Programming Contest）C]

https://beta.atcoder.jp/contests/bitflyer2018-qual/tasks/bitflyer2018_qual_c

考察

1. まずはどこかを全探索する
2. とりあえずiの位置を全探索してみるが、jの位置によってkの範囲が変わるので無理そう
3. jの位置を全探索してみると、iとkを取る範囲は特定できるが、iとkの距離をうまく扱えない感じがある
4. ＝＝＝ここで一旦Dを通して帰ってくる＝＝＝
5. jの位置を全探索すると、条件を満たさない組なら高速に求めることができそう
6. 条件を満たさない組の個数を求めることにしよう
7. これならできる

前提知識

• しゃくとり法

解説

https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2599738

条件を満たすものの個数を(全組み合わせ)-(条件を満たさない組み合わせ)で求める方針でやろう。
まずは事前に配列A,Bをしゃくとり法を使って事前計算しておこう。
A[i] := X[i]より左側で差がD以下の要素が何個あるか
B[i] := X[i]より右側で差がD以下の要素が何個あるか
　
条件を満たさない組み合わせは以下の4つがある
1. X[i]とX[k]の差がD以下
2. X[i]とX[k]の差がDより大きいが、X[i]とX[j]の差だけがDより大きい
3. X[i]とX[k]の差がDより大きいが、X[j]とX[k]の差だけがDより大きい
4. X[i]とX[k]の差がDより大きいが、X[i]とX[j]の差とX[j]とX[k]の差の両方がDより大きい
　
1はkを全探索する。
すると、iとjはA[k]から2つ選ぶ必要があるので、C(A[k],2)=A[k]*(A[k]-1)/2
　
2以降はjを全探索する。
jを固定すると、iの候補がA[j]個、kの候補がB[j]個となる。
iになれるが差がDより大きい個数をn, kになれるが差がDより大きい個数をmとすると、
2はn*B[j]
3はA[j]*m
4はn*m
となり、これを引いていく。
　
全組み合わせはC(N,3)=N*(N-1)*(N-2)/6なので、ここから4つを引いたら答え。

ll N, D, X[101010];
ll A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;
    rep(i, 0, N) cin >> X[i];
 
    ll ans = N * (N - 1) * (N - 2) / 6;
 
    int L = 0;
    rep(R, 0, N) {
        while (L < R and D < X[R] - X[L]) L++;
        A[R] = R - L;
    }
 
    int R = N - 1;
    rrep(L, N - 1, 0) {
        while (L < R and D < X[R] - X[L]) R--;
        B[L] = R - L;
    }
 
    rep(i, 0, N) {
        ans -= A[i] * (A[i] - 1) / 2; // 1
 
        ll n = i - A[i];
        ll m = N - (i + 1) - B[i];
 
        ans -= n * m; // 4
        ans -= n * B[i]; // 2
        ans -= A[i] * m; // 3
    }
 
    cout << ans << endl;
}