meaning of the title

Title Link

Sol

Why don't you solve the problem.

In general, it is not difficult to think of monotonic data structure when considering the contribution of maximum value

For this problem, we can preprocess the first position larger than him on the left and the first position larger than him on the right

Then \ ((l_i, r_i) \) will generate \ (p1 \) contribution

\([l_i + 1, i - 1] \) and \ (r_i \) contribute \ (p2 \)

\([i + 1, r_i - 1] \) and \ (l_i \) contribute \ (p2 \)

In this way, we can calculate the contribution of each point directly by adding the segment tree.

Then the statistical answer is very immortal. We split the inquiry. When enumeration to \ (l - 1 \), remember that \ (sum \) of \ ([l,r] \) is \ (s1 \), when enumeration to \ (r \), remember that \ (sum \) of \ ([l,r] \) is s2, then the answer of the inquiry is \ (s2 - s1 \)

Complexity: \ (O(nlogn) \)

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, p1, p2, a[MAXN], L[MAXN], R[MAXN];
LL ans[MAXN];
int ll[MAXN], rr[MAXN];
LL sum[MAXN], f[MAXN];
#define ls k << 1
#define rs k << 1 | 1
void ps(int k, int v) {
    sum[k] += (rr[k] - ll[k] + 1) * v;
    f[k] += v;
}
void pushdown(int k) {
    if(!f[k]) return ;
    ps(ls, f[k]); ps(rs, f[k]);
    f[k] = 0;
}
void update(int k) {
    sum[k] = sum[ls] + sum[rs];
}
void Build(int k, int l, int r) {
    ll[k] = l; rr[k] = r;
    if(l == r) return ;
    int mid = l + r >> 1;
    Build(ls, l, mid); Build(rs, mid + 1, r);
}
void IntAdd(int k, int l, int r, int ql, int qr, int v) {
    if(ql > qr) return ;
    if(ql <= l && r <= qr) {ps(k, v); return ;}
    pushdown(k);
    int mid = l + r >> 1;
    if(ql <= mid) IntAdd(ls, l, mid, ql, qr, v);
    if(qr  > mid) IntAdd(rs, mid + 1, r, ql, qr, v);
    update(k);
}
LL IntQuery(int k, int l, int r, int ql, int qr) {
    if(ql > qr) return 0;
    if(ql <= l && r <= qr) return sum[k];
    pushdown(k);
    int mid = l + r >> 1;
    if(ql > mid) return IntQuery(rs, mid + 1, r, ql, qr);
    else if(qr <= mid) return IntQuery(ls, l, mid, ql, qr);
    else return IntQuery(ls, l, mid, ql, qr) + IntQuery(rs, mid + 1, r, ql, qr);
}
struct Query {
    int l, r, val, id;
    bool operator < (const Query &rhs) const {
        return id < rhs.id;
    }
};
vector<Query> q[MAXN];
void Pre() {
    a[0] = INF; a[N + 1] = INF;
    static int st[MAXN], top = 0;
    for(int i = 1; i <= N + 1; i++) {
        while(top && a[i] > a[st[top]]) R[st[top--]] = i;
        L[i] = st[top];
        st[++top] = i;
    }
    for(int i = 1; i <= N; i++) {
        q[R[i]].push_back({L[i], L[i], p1, -R[i]});
        q[L[i]].push_back({i + 1, R[i] - 1, p2, -L[i]});
        q[R[i]].push_back({L[i] + 1, i - 1, p2, -R[i]});
    }
}

int main() {
    N = read(); M = read(); p1 = read(); p2 = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    Pre();
    Build(1, 0, N + 1);
    for(int i = 1; i <= M; i++) {
        int a = read(), b = read();
        ans[i] = (b - a) * p1;
        q[a - 1].push_back({a, b, -1, i});
        q[b].push_back({a, b, 1, i});
    }
    for(int i = 0; i <= N; i++) {
        sort(q[i].begin(), q[i].end()); 
        for(auto &x : q[i]) {
            if(x.id < 0) IntAdd(1, 0, N + 1, x.l, x.r, x.val);
            else ans[x.id] += 1ll * x.val * (IntQuery(1, 0, N + 1, x.l, x.r));
        }
    }
    for(int i = 1; i <= M; i++) cout << ans[i] << "\n";
    return 0;
}