CF601B Lipshitz Sequence 题解

给你一个序列 \(v_{1 \dots n}\)，定义 \(f(v)\) 为 \(v\) 中斜率最大值（\(\lvert v \rvert = 1\) 则 \(f(v)=0\)），有 \(q\) 组询问，每次给定 \(1 \le l \lt r \le n\)，求 \(a_{l \dots r}\) 的每个子区间的 \(f\) 之和。

一个关键的性质是，最大的斜率只在相邻数间取到。

有了这个性质，这题就可以秒了。证明留作练习（

#include <iostream>
#include <vector>
#include <stack>
#define UP(i,s,e) for(auto i=s; i<e; ++i)
using std::cin; using std::cout;
namespace m{ // }{{{
constexpr int N = 1e5;
using ll = long long;
int in, iq;
int ia[N];
void solve(){
    int il, ir; cin >> il >> ir; il--;
    std::stack<std::pair<int, int>> last; // k, place
    last.push({998244353, il-1});
    ll lastval = 0, ans = 0;
    UP(i, il, ir-1){
        int k = (std::abs(ia[i+1]-ia[i]));
        while(last.top().first < k){
            int k1 = last.top().first;
            int e1 = last.top().second;
            last.pop();
            lastval -= k1 * 1ll * (e1-last.top().second);
        }
        lastval += (i-last.top().second) * 1ll * k;
        last.push({k, i});
        ans += lastval;
    }
    cout << ans << '\n';
}
void work(){
    cin >> in >> iq;
    UP(i, 0, in){
        cin >> ia[i];
    }
    UP(i, 0, iq) solve();
}
} // {}}}
int main(){m::work(); return 0;}