• \(f(x)\coloneqq\) 睡眠記録を取り始めてから \(x\) 分後までに何分寝たか \(\ (0\leq x\leq A _ N)\)

を求めることができたら、クエリの答えは \(f(r _ i)-f(l _ i)\) として計算できます。

\(f(x)\) は \(A _ i\leq x\leq A _ {i+1}\) の範囲では一次関数になっていることに注意すると、次のような方針で \(f(x)\) の値が高速に求められます。

1. 事前に \(f(A _ i)\ (1\leq i\leq N)\) の値をすべて求めておく。
2. \(A _ j\leq x\leq A _ {j+1}\) となるような \(j\) を求める。
3. \(f(A _ j),f(A _ {j+1})\) の値から \(f(x)\) の値を求める。

\(f(A _ i)\ (1\leq i\leq N)\) の値は、\(i\) の昇順に計算することで全体で \(O(N)\) 時間で求められます。

\(A _ j\leq x\leq A _ {j+1}\) であるような \(j\) は二分探索を使って \(O(\log N)\) 時間で求められます。

\(f(x)=f(A _ j)+(x-A _ j)\dfrac{f(A _ {j+1})-f(A _ j)}{A _ {j+1}-A _ j}\) の計算は定数時間で可能です。

よって、この問題を \(O(N+Q\log N)\) 時間で解くことができました。
クエリを先読みしてソートすることで \(O(N+Q\log Q)\) 時間で解くこともできます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;

    unsigned N;
    cin >> N;
    vector<unsigned> A(N), fA(N);
    for (auto &&a : A)
        cin >> a;

    // fA[i] := A[i] 分までに何分寝たか
    for (unsigned i = 1; i < N; ++i)
        if (i % 2 == 0)
            fA[i] = fA[i - 1] + A[i] - A[i - 1];
        else
            fA[i] = fA[i - 1];

    unsigned Q;
    cin >> Q;

    // f(x) := x 分までに何分寝たか
    auto f{[&A, &fA](auto x) -> unsigned {
        const auto j = upper_bound(begin(A) + 1, end(A), x) - begin(A) - 1;
        return fA[j] + (fA[j + 1] - fA[j]) / (A[j + 1] - A[j]) * (x - A[j]);
    }};
    for (unsigned i = 0; i < Q; ++i) {
        unsigned l, r;
        cin >> l >> r;
        cout << f(r) - f(l) << endl;
    }

    return 0;
}