D - 通勤 CODE FESTIVAL 2018 qual A

D - 通勤
問題概略
x軸上にN個のガソリンスタンドがあり、D地点にゴールがある。
地点0から燃料Fでスタートし、燃料がT未満でスタンドに着いた時、Fまで補充する。
ガソリンスタンドをいくつか壊した時、ゴールまでたどり着ける組み合わせはいくつか。

解法
dp[i] := 最後に補給した地点がiとなるまでの組み合わせとする。
iから見て、燃料が補給できない、距離がF-T以内の地点はどのような配置でも後々の燃料に関係ないため自由における。
よってL[i]:=燃料が補給できる最小地点 R[i]:=燃料が補給できない最小値点として
L[i] <= j < R[i]なるjにdp[i] * pow(2,自由における数)を遅延評価セグメント木で加算してやれば遷移できる。
ゴールへ行ける時、燃料が補給できるかに関わらずゴール地点を加算する必要があるが、これはL[i] = min(L[i],Dの添字)としておけばよい。
こうすれば、上でやりたいことが実現できる。
dp[Dの添字]が答え

class SegmentLazyMod {
    long[] lazy;
    long[] sums;
    int N, MOD = (int) 1e9 + 7;

    SegmentLazyMod(long[] nums) {
        int n = nums.length;
        N = 1;
        while (N < n) N *= 2;
        sums = new long[N * 2];
        lazy = new long[N * 2];
        //初期値をセット
        for (int i = 0; i < nums.length; i++) {
            sums[i + N - 1] = nums[i] % MOD;
        }

        //初期値を計算
        //下から2段目右端から左へ、上へ
        for (int i = N - 2; i >= 0; i--) {
            sums[i] = mSum(sums[i * 2 + 1], sums[i * 2 + 2]);
        }
    }

    SegmentLazyMod(int len) {
        int n = len;
        N = 1;
        while (N < n) N *= 2;
        sums = new long[N * 2];
        lazy = new long[N * 2];
    }

    public void add(int index, long addValue) {
        add(index, index + 1, addValue, 0, 0, N);
    }

    public void add(int start, int end, long addValue) {
        add(start, end, addValue, 0, 0, N);
    }

    //[a b)にxを加算する 添字はiで　l rの区間を今見ている
    private void add(int a, int b, long x, int i, int l, int r) {
        //完全に含む
        if (a <= l && r <= b) {
            lazy[i] = mSum(lazy[i], x);
        }
        //一部でも含む
        else if (a < r && l < b) {
            sums[i] = mSum(sums[i], mMul((Math.min(b, r) - Math.max(a, l)), x));
            add(a, b, x, i * 2 + 1, l, (l + r) / 2);
            add(a, b, x, i * 2 + 2, (l + r) / 2, r);
        }
    }

    public long get(int index) {
        return sum(index, index + 1, 0, 0, N);
    }

    public long sum(int start, int end) {
        return sum(start, end, 0, 0, N);
    }

    private long sum(int a, int b, int i, int l, int r) {
        //完全に含まれる
        if (a <= l && r <= b) {
            return mSum(mMul((r - l), lazy[i]), sums[i]);
        }
        //一部一致
        else if (a < r && l < b) {
            long res = 0;
            res = mSum(res, mMul(Math.min(b, r) - Math.max(a, l), lazy[i]));
            res = mSum(res, sum(a, b, i * 2 + 1, l, (l + r) / 2));
            res = mSum(res, sum(a, b, i * 2 + 2, (l + r) / 2, r));
            return res;
        } else {
            return 0;
        }
    }

    public int mSum(long a, long b) {
        return (int) (((a % MOD + b % MOD) % MOD + MOD) % MOD);
    }

    public int mMul(long a, long b) {
        return (int) (((a % MOD * b % MOD) % MOD + MOD) % MOD);
    }
}
public class Main {
    static int N;
    static int[] A;

    public static void solve() throws Exception {
        int D = ni();
        int F = ni();
        int T = ni();
        int N = ni();
        long[] X = new long[N + 2];
        for (int i = 0; i < N; i++) {
            X[i + 1] = ni();
        }
        X[N + 1] = D;
        //半開区間
        int[] L = new int[N + 1];
        int[] R = new int[N + 1];
        for (int i = 0; i < N + 1; i++) {
            L[i] = upperBound(X, X[i] + (F - T));
            L[i] = min(L[i], N + 1);
            R[i] = upperBound(X, X[i] + F);
        }
        SegmentLazyMod seg = new SegmentLazyMod(N + 2);
        //[i] := 最後にiで補給する時のそれまでの場合の数  配るDPで
        int[] dp = new int[N + 2];
        seg.add(0, 1);
        for (int i = 0; i < N + 1; i++) {
            dp[i] = (int) seg.sum(i, i + 1);
            int fact = mPow(2, L[i] - i - 1);
            seg.add(L[i], R[i], mMul(dp[i], fact));
        }
        System.out.println(seg.get(N + 1));
    }
 public static int upperBound(final long[] arr, final long value) {
        int low = 0;
        int high = arr.length;
        int mid;
        while (low < high) {
            mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
            if (arr[mid] <= value) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}