CFR 602 D. Lipshitz Sequence ( Segment Tree )

Problem - D - Codeforces
It is well known fact that only the adjacent elements would have the maximum slope. Making use of this fact, we can always find the maximum slope, find all subsequences it will contribute to, then apply divide and conquer on both sides. O( q * n lg n ).

struct itvt{
    int mxv, pmxv;
    int lb, rb;
    itvt *lc, *rc;
    itvt( int _l = -1, int _r = -1 ): lb(_l), rb(_r), lc(NULL), rc(NULL){}
    void pull(){
        mxv = -INF;
        if( upmax( mxv, lc->mxv ) ) pmxv = lc->pmxv;
        if( upmax( mxv, rc->mxv ) ) pmxv = rc->pmxv;
    }
    void update(int k, int x){
        if( lb == rb ){
            mxv = x;
            return;
        }
        int mid = lb + rb >> 1;
        if( k <= mid ) lc->update( k, x );
        else rc->update( k, x );
        pull();
    }
    pii qmax(int ql, int qr){
        if( qr < lb || rb < ql ) return pii( -INF, -INF );
        if( ql <= lb && rb <= qr ) return pii( mxv, pmxv );
        return max( lc->qmax( ql, qr ), rc->qmax( ql, qr ) );
    }
} *root;

const int MAXN = 1e5 + 5;
const int MAXQ = 100 + 2;
const int MAXA = 1e8 + 8;

int diff[ MAXN ];

itvt* buildItvt( int lb, int rb ){
    itvt *t = new itvt( lb, rb );
    if( lb == rb ){
        t->mxv = diff[ lb ];
        t->pmxv = lb;
        return t;
    }
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    t->pull();
    return t;
}

int n, q;
int a[ MAXN ];

void init(){
    scanf("%d%d", &n, &q);
    rep( i, 0, n ) scanf("%d", a + i);
}

ll dc(int ql, int qr){
    if( ql >  qr ) return 0;
    if( ql == qr ) return root->qmax( ql, qr ).first;
    pii rmx = root->qmax( ql, qr );
    int idx = rmx.second;
    ll res = 1LL * ( idx - ql + 1 ) * ( qr - idx + 1 ) * rmx.first;
    res += dc( ql, idx - 1 );
    res += dc( idx + 1, qr );
    return res;
}

void solve(){
    rep( i, 0, n - 1 ) diff[ i ] = abs( a[ i + 1 ] - a[ i ] );
    root = buildItvt( 0, n - 1 );
    while( q-- ){
        int ql, qr; scanf("%d%d", &ql, &qr);
        --ql, --qr;
        ll ans = dc( ql, qr - 1 );
        printf("%lld\n", ans);
    }
}