2018 codeFlyer 予選 C 徒歩圏内 (400 点)

実装力って大事だなと。

Before: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2601840
After: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2603569

• 問題へのリンク

問題概要

長さ の単調増加数列 が与えられる。添字 の組で

• < <
• 
• 
• >

を満たすものを数え上げよ。

制約

• 3 <= N <= 10⁵

解法

1. X[j] - X[i] <= D かつ X[k] - X[j] <= D を満たす場合の数
2. X[k] - X[i] <= D を満たす場合の数

をそれぞれ求めて、1 から 2 を引けば良い。
これらを求めるために、しゃくとり法によって以下を求めておく

• L[i] := (X[i] - X[left] <= D となるような最小の left)
• R[i] := (X[right] - X[i] <= D となるような最大の right)

1 は、j を固定して求める。
(R[j] - j) * (j - L[j]) を各 j に対して総和をとる

2 は、i を固定して求める (これを j を固定してやろうとして実装が煩雑になってしまった！！！！！！！！！！！！！)
R[i] - i 個から 2 個選ぶ問題になる。(R[i] - i) * (R[i] - i - 1) / 2 を各 i に対して総和をとる

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, D;
    cin >> N >> D;
    vector<long long> X(N);
    for (int i = 0; i < N; ++i) cin >> X[i];
    
    vector<long long> L(N), R(N);
    int left = 0, right = 0;
    for (int mid = 0; mid < N; ++mid) {
        while (right < N && X[right] - X[mid] <= D) ++right;
        while (left < mid && X[mid] - X[left] > D) ++left;
        R[mid] = right - 1;
        L[mid] = left;
    }
    
    long long res = 0;
    for (long long mid = 0; mid < N; ++mid) res += (R[mid] - mid)  * (mid - L[mid]);
    for (long long left = 0; left < N; ++left) res -= (R[left] - left) * (R[left] - left - 1) / 2;
    cout << res << endl;
}