Codeforces Round #333 (Div. 1) B. Lipshitz Sequence

問題

codeforces.com

解法

i と j が 2 以上離れている整数の組(i, j) について, |h[i]-h[j]|/|i-j| が L(h) として採用されることは無いです。つまり, i と i+1 について, |h[i+1]-h[i]| という値のみ考えれば良く, 他の値は無視して構わないです。

あとやるべきことは, 各区間 [l, r] について, L(h) の値として |h[i+1]-h[i]| が採用されるような部分区間がいくつあるのかを O(N) で求める作業です。これは, 前やった問題に似ています。mayokoex.hatenablog.com
この問題の解法とほとんど同じですが, 一つ注意なのは, 同じ値の扱いです。|h[i+1]-h[i]| の値と |h[j+1]-h[j]| の値が一致している場合, (i, i+1) の方からは (j, j+1) も含むように部分区間をとっても良いですが, その場合(j, j+1) の方から (i, i+1) の区間も含むように 部分区間を取ってはいけません。
i < j の場合は (i, i+1) からだけ (j, j+1) の区間をとっても良いことにすれば OK です。

const int MAXN = 100010;
int a[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> b(n-1);
    for (int i = 0; i < n-1; i++) b[i] = abs(a[i]-a[i+1]);
    while (m--) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        vector<int> c(r-l);
        for (int i = l; i < r; i++) c[i-l] = b[i];
        vector<ll> L(r-l), R(r-l);
        {
            stack<pii> st;
            int cur = 0;
            while (cur < r-l) {
                st.push(pii(c[cur], cur));
                int i = cur+1;
                while (i < r-l && st.top().first >= c[i]) {
                    st.push(pii(c[i], i));
                    i++;
                }
                while (i < r-l && !st.empty() && st.top().first < c[i]) {
                    pii p = st.top(); st.pop();
                    L[p.second] = i-p.second;
                }
                cur = i;
            }
            while (!st.empty()) {
                pii p = st.top(); st.pop();
                L[p.second] = r-l-p.second;
            }
        }
        reverse(c.begin(), c.end());
        {
            stack<pii> st;
            int cur = 0;
            while (cur < r-l) {
                st.push(pii(c[cur], cur));
                int i = cur+1;
                while (i < r-l && st.top().first > c[i]) {
                    st.push(pii(c[i], i));
                    i++;
                }
                while (i < r-l && !st.empty() && st.top().first <= c[i]) {
                    pii p = st.top(); st.pop();
                    R[p.second] = i-p.second;
                }
                cur = i;
            }
            while (!st.empty()) {
                pii p = st.top(); st.pop();
                R[p.second] = r-l-p.second;
            }
        }
        reverse(c.begin(), c.end());
        reverse(R.begin(), R.end());
        ll ans = 0;
        for (int i = 0; i < r-l; i++) {
            ans += c[i] * R[i] * L[i];
        }
        cout << ans << endl;
    }
    return 0;
}