Blog

题目

Luogu
LOJ
Acwing

思路

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int N = 200010;
int n, m, P1, P2, L[N], R[N], a[N];
struct QUERY { int key, l, r, v, id; } Q[N * 2];
bool operator<(QUERY a, QUERY b) { return a.key < b.key; }
struct LINE { int key, l, r, v; } P[N * 3];
bool operator<(LINE a, LINE b) { return a.key < b.key; }
int stk[N], top, cnt_q, cnt_l, ans[N];
/*----------------线段树---------------------*/
struct NODE { int l, r, sum, add; } tr[N * 4];
void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; }
void add(int u, int c) { tr[u].add += c, tr[u].sum += (tr[u].r - tr[u].l + 1) * c; }
void pushdown(int u) { add(u << 1, tr[u].add), add(u << 1 | 1, tr[u].add), tr[u].add = 0; }
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r, tr[u].add = tr[u].sum = 0;
    if (l >= r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void modify(int u, int l, int r, int c) {
    if (tr[u].l >= l && tr[u].r <= r) 
        return tr[u].add += c, tr[u].sum += (tr[u].r - tr[u].l + 1) * c, void(0);
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) modify(u << 1, l, r, c);
    if (r > mid) modify(u << 1 | 1, l, r, c);
    pushup(u);
}
int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1, res = 0;
    if (l <= mid) res += query(u << 1, l, r);
    if (r > mid) res += query(u << 1 | 1, l, r);
    return res;
}
/*-------------------------------------------*/
signed main() {
    cin >> n >> m >> P1 >> P2;
    for (int i = 1; i <= n; i++) cin >> a[i];
    /*-----------------预处理 L, R --------------*/
    top = 0, stk[0] = 0;
    for (int i = 1; i <= n; i++) {
        while (top && a[stk[top]] <= a[i]) top--;
        L[i] = stk[top], stk[++top] = i;
    } 
    top = 0, stk[0] = n + 1;
    for (int i = n; i >= 1; i--) {
        while (top && a[stk[top]] <= a[i]) top--;
        R[i] = stk[top], stk[++top] = i;
    }
    /*-------------------------------------------*/
    // 把询问拆开
    for (int i = 1, l, r; i <= m && cin >> l >> r; i++)  
        Q[++cnt_q] = (QUERY) { r, l, r, 1, i },
        Q[++cnt_q] = (QUERY) { l - 1, l, r, -1, i },
        ans[i] = (r - l) * P1; // 初始化一下
    sort(Q + 1, Q + cnt_q + 1);
    // 把每个点拆开
    for (int i = 1; i <= n; i++) {
        // 判断 L, R 是否存在
        if (L[i] && R[i] < n + 1) P[++cnt_l] = (LINE) { R[i], L[i], L[i], P1 };
        // 防止 i + 1 > R[i] - 1, 下面同理
        if (L[i] && R[i] > i + 1) P[++cnt_l] = (LINE) { L[i], i + 1, R[i] - 1, P2 };
        if (L[i] + 1 < i && R[i] < n + 1) P[++cnt_l] = (LINE) { R[i], L[i] + 1, i - 1, P2 };
    }
    sort(P + 1, P + cnt_l + 1);
    build(1, 1, n);
    for (int i = 1, j = 1; i <= cnt_q; i++) {
        // 把当前 询问区间加入位置的条件 之前 的点都加上贡献
        while (j <= cnt_l && P[j].key <= Q[i].key) modify(1, P[j].l, P[j].r, P[j].v), j++;
        ans[Q[i].id] += Q[i].v * (query(1, Q[i].l, Q[i].r)); //更新答案
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << endl;
    return 0;
}