久しぶりに JOI の重たい問題が解けた！

問題概要（意訳）

正の整数 $D$ が与えられる。

一般に、 $0$ 以上の整数からなる長さ $M$ の数列 $A_{1}, A_{2}, \dots, A_{M}$ に対して、次の操作を繰り返すことによって広義単調増加であるようにすることが可能であるとき、 $f_{D}(A)$ をその操作回数の最小値とし、不可能であるとき $f_{D}(A) = -1$ とする。

操作：数列 A の要素を 1 つ選び、 $D$ を引く (ただし、負になる場合にはこの操作はできない)

さて、長さ $N$ の数列 $C_{1}, C_{2}, \dots, C_{N}$ が入力として与えられるので、以下の $Q$ 個のクエリに答えよ：

「各クエリでは整数 $L, R$ ( $1 \le L \le R \le N$ ) が与えられるので、 $f_{D}(C_{L}, C_{L+1}, \dots, C_{R})$ を求めよ」

制約

$1 \le N, Q \le 300000$
$1 \le D \le 10^{12}$
$0 \le C_{i} \le 10^{12}$

考えたこと：まずはクエリでないバージョンを解く

まずは、クエリではないバージョンの問題を解くことを考える。つまり、一般に数列 $A$ に対して $f_{D}(A)$ を求める方法を考える。

たとえば、 $D = 3$ 、 $A = (8, 11, 7, 18, 29, 19)$ のとき、右から順に見ていき、「右隣の値より小さい範囲で最大の数にする」という Greedy に基づく解法でよい。

なお、小課題 1 はこの解法で正解できる。

右端を右へずらしていく

それでは、クエリに対処していく。ここでは、区間の右端を徐々に右にずらしていくことを考える。

数列 $C$ の区間 $\lbrack 0, r)$ を最適にした状態（ $i$ 番目の要素 $C_{i}$ は操作後に $A_{i}$ になるとする）から、区間 [0, r+1) を最適にする際の差分に着目しよう。

$A_{r-1} \le C_{r}$ のとき：既存の数列 $A$ には特に修正を加えず、値 $C_{r}$ が末尾に加わる
$A_{r-1} \gt C_{r}$ のとき：既存の数列 $A$ の末尾の値が $C_{r}$ 以下になるように操作を繰り返して、 $A$ の残りの要素についても同様に操作を繰り返していく

後者について、もし既存の数列 $A$ のどの隣接する要素の差も $D$ 未満であったならば、下の図のように、一様に $A$ の各要素から同じ回数分だけ操作を実行することになる。（0 未満になる部分があっても一旦気にしないこととする）

次に、もし既存の数列 $A$ において、隣接する要素が $D$ 以上の箇所があれば、「隣接する要素の右側から何回まで $D$ を引いても単調増加性が壊れないか」を示す値を管理しよう。この値を用いることで、下の図のように、既存の数列 $A$ の各要素に対する操作回数が、右から順に確定していくことが分かる。

したがって、次のデータ構造を毎回更新していけばよいことがわかった。

操作後の数列 $A$ (区間加算のできるセグ木・BIT)
操作後の数列 $A$ について、差が $D$ 以上であるような隣接 2 要素についての、「隣接する要素の右側に対して何回まで $D$ を引いても単調増加性が壊れないか」を管理する値

前者については、一律に同じ値を減算する部分を遅延評価セグメント木または BIT で実現する。

ここで後者について考えると、右端が広がっていく際に、一度差が $D$ 未満になった隣接要素については、二度と差が $D$ 以上になることはない。したがって、前者の「一律に同じ値を減算する」の発生回数は高々 $O(N+Q)$ 回に抑えられる。

以上から、全体として $O((N+Q)\log N)$ の計算量で問題を解くことができた。

コード

僕の実装だと、long long 型を使うとオーバーフローしてしまったので、int128__ 型を使った。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
using pll = pair<ll, ll>;
using tll = array<ll, 3>;
using vll = vector<ll>;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

// output
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }

// int 128
i128 to_integer(const string &s) {
    i128 res = 0;
    for (auto c : s) {
         if (isdigit(c)) res = res * 10 + (c - '0');
    }
    if (s[0] == '-') res *= -1;
    return res;
}
istream& operator >> (istream &is, i128 &x) {
    string s;
    is >> s;
    x = to_integer(s);
    return is;
}
ostream& operator << (ostream &os, const i128 &x) {
    i128 ax = (x >= 0 ? x : -x);
    char buffer[128];
    char *d = end(buffer);
    do {
         --d;
        *d = "0123456789"[ax % 10];
        ax /= 10;
    } while (ax != 0);
    if (x < 0) {
        --d;
        *d = '-';
    }
    int len = end(buffer) - d;
    if (os.rdbuf()->sputn(d, len) != len) {
        os.setstate(ios_base::badbit);
    }
    return os;
}

// Range Add Range sum
template<class Abel> struct RangeAddRangeSum {
    Abel UNITY_SUM = 0;
    vector<Abel> dat[2];

    // [0, n)
    RangeAddRangeSum(int n, Abel unity = 0) : UNITY_SUM(unity) {
        init(n);
    }
    void init(int n) {
        for (int iter = 0; iter < 2; ++iter)
            dat[iter].assign(n + 1, UNITY_SUM);
    }
    int size() const {
        return (int)dat[0].size();
    }
    
    // [a, b), a and b are 0-indexed
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i |= i + 1)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * (-a));
        sub_add(1, a, x);
        sub_add(0, b, x * b);
        sub_add(1, b, x * (-1));
    }
    
    // [a, b), a and b are 0-indexed
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a - 1; i >= 0; i = (i & (i + 1)) - 1)
            res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b)
            + sub_sum(1, b) * b
            - sub_sum(0, a)
            - sub_sum(1, a) * a;
    }
    inline Abel operator [] (int i) {
        return sum(i, i + 1);
    }
    
    // debug
    friend ostream& operator << (ostream &s, RangeAddRangeSum bit) {
        for (int i = 0; i < (int)bit.size(); ++i) s << bit[i] << " ";
        return s;
    }
};


int main() {
    i128 N, D, Q; cin >> N >> D;
    vector<i128> C(N);
    for (int i = 0; i < N; i++) cin >> C[i];
    cin >> Q;
    vector<i128> L(Q), R(Q), res(Q, -1);
    vector<vector<pair<i128,i128>>> qs(N+1);
    for (int q = 0; q < Q; q++) {
        cin >> L[q] >> R[q], L[q]--, qs[R[q]].emplace_back(L[q], q);
    }
    
    RangeAddRangeSum<i128> cnt(N, 0), A(N, 0);
    deque<pair<i128,i128>> walls;
    for (int r = 0; r < N; r++) {
        A.add(r, r+1, C[r]);
        if (r >= 1 && C[r] >= A[r-1] + D) walls.emplace_back(r, (C[r] - A[r-1]) / D);
        if (r >= 1 && C[r] < A[r-1]) {
            i128 need = (A[r-1] - C[r] + D - 1) / D, right = r;
            while (!walls.empty() && need > 0) {
                auto [left, rem] = walls.back(); 
                walls.pop_back();
                A.add(left, right, -D * need), cnt.add(left, right, need);
                i128 sub = min(rem, need);
                rem -= sub, need -= sub;
                if (rem > 0) walls.emplace_back(left, rem);
                right = left;
            }
            if (need > 0) A.add(0, right, -D * need), cnt.add(0, right, need);
        }
        for (auto [l, id] : qs[r+1]) if (A[l] >= 0) res[id] = cnt.sum(l, r+1);
    }
    for (auto val : res) cout << val << endl;
}