"我已经想到了一个绝妙的证明, 可惜这里空间太小, 写不下" by 费马

"我昨天就已经想到了一个绝妙的解法, 可惜我老年痴呆, 忘了" by 宽嫂

懵逼的 题目

BZOJ

扯淡的 题解

这种题基本上都要先求出来premax, nexmax之类的…

一开始思维江化, 老是想着怎么以每个点为端点, 然后取算贡献…对整个区间做还好说…区间询问就抓瞎了…

然后抄neither_nor大爷的题解, 感觉非常的神仙

以每个数为要求的区间中的最大值(不含端点), 这样一来就好办了, 对于每个数来说:

  • 第一种情况就是点对[premax[i], nexmax[i]]
  • 第二种情况就是点对[premax[i], j], $j \in [i + 1, nexmax_i - 1]$(显然这个区间里没有比a[i]还大的数了), 和[j, nexmax[i]], $j \in[premax_i + 1, i - 1]$

然后我们就是搞出了一些区间, 要求左端点大于某个数, 右端点小于某个数的区间权值和, 就是二维数点呗

我用的扫描线, 第二种情况比较复杂, 因为在二维平面上线段的方向不一样, 我们就把他拆开来做, 横着扫一遍竖着扫一遍

最后别忘了对每个区间加上ta的区间长度减1个$p_1$(只有两个数的区间也满足情况1)

然后就没有然后了….

沙茶的 代码

想清楚怎么实现之后代码似乎不难写…

/**************************************************************
    Problem: 4826
    User: Cansult
    Language: C++
    Result: Accepted
    Time:5996 ms
    Memory:41140 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define MAXN (200000 + 5)
#define INF (0x7fffffff)
#define pii pair<int, int>
#define LL long long
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
using namespace std;
struct edg {
    int le, ri;
    LL zh, lazy;
} b[MAXN << 2];
struct question {
    int le, ri, time, type, zh;
    question() {}
    question(int l, int r, int ti, int ty, int z) : le(l), ri(r), time(ti), type(ty), zh(z) {}
} que[MAXN << 2];
int n, q, cntq, a[MAXN], p1, p2, premax[MAXN], nexmax[MAXN];
LL ans[MAXN];
pii sq[MAXN];
void js(int dq, int le, int ri) {
    b[dq].le = le, b[dq].ri = ri, b[dq].zh = b[dq].lazy = 0;
    if (le == ri)
        return;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
}
void push_down(int dq) {
    LL x = b[dq].lazy;
    b[LS(dq)].lazy += x, b[RS(dq)].lazy += x;
    b[LS(dq)].zh += (b[LS(dq)].ri - b[LS(dq)].le + 1) * x;
    b[RS(dq)].zh += (b[RS(dq)].ri - b[RS(dq)].le + 1) * x;
    b[dq].lazy = 0;
}
LL cx(int dq, int le, int ri) {
    if (le > b[dq].ri || le > ri || ri < b[dq].le)
        return 0;
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq].zh;
    if (b[dq].lazy)
        push_down(dq);
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        return cx(RS(dq), le, ri);
    else if (ri <= mi)
        return cx(LS(dq), le, ri);
    else
        return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, LL zh) {
    if (le > b[dq].ri || le > ri || ri < b[dq].le)
        return;
    if (b[dq].le == le && b[dq].ri == ri) {
        b[dq].lazy += zh;
        b[dq].zh += (ri - le + 1) * zh;
        return;
    }
    if (b[dq].lazy)
        push_down(dq);
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        xg(RS(dq), le, ri, zh);
    else if (ri <= mi)
        xg(LS(dq), le, ri, zh);
    else
        xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
    b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}
bool cmp(const question& x, const question& y) {
    if (x.time == y.time)
        return x.type > y.type;
    return x.time < y.time;
}
bool cmp2(const question& x, const question& y) {
    if (x.time == y.time)
        return x.type > y.type;
    return x.time > y.time;
}
void solve() {
    for (int i = 1; i <= n; i++) {
        que[++cntq] = question(premax[i], premax[i], nexmax[i], 1, p1);
        que[++cntq] = question(premax[i] + 1, i - 1, nexmax[i], 1, p2);
    }
    for (int i = 1; i <= q; i++) que[++cntq] = question(sq[i].first, n, sq[i].second, 0, i);
    sort(que + 1, que + cntq + 1, cmp);
    js(1, 1, n);
    for (int i = 1; i <= cntq; i++)
        if (que[i].type)
            xg(1, que[i].le, que[i].ri, que[i].zh);
        else
            ans[que[i].zh] += cx(1, que[i].le, que[i].ri);

    cntq = 0;
    for (int i = 1; i <= n; i++) que[++cntq] = question(i + 1, nexmax[i] - 1, premax[i], 1, p2);
    for (int i = 1; i <= q; i++) que[++cntq] = question(1, sq[i].second, sq[i].first, 0, i);
    sort(que + 1, que + cntq + 1, cmp2);
    js(1, 1, n);
    for (int i = 1; i <= cntq; i++)
        if (que[i].type)
            xg(1, que[i].le, que[i].ri, que[i].zh);
        else
            ans[que[i].zh] += cx(1, que[i].le, que[i].ri);

    for (int i = 1; i <= q; i++) ans[i] += (sq[i].second - sq[i].first) * p1;
}
stack<pii> bGary;
int solve(pii x) {
    while (bGary.top().first < x.first) bGary.pop();
    int re = bGary.top().second;
    bGary.push(x);
    return re;
}
void init() {
    bGary.push(make_pair(INF, 0));
    for (int i = 1; i <= n; i++) premax[i] = solve(make_pair(a[i], i));
    while (!bGary.empty()) bGary.pop();
    bGary.push(make_pair(INF, n + 1));
    for (int i = n; i >= 1; i--) nexmax[i] = solve(make_pair(a[i], i));
    for (int i = 1; i <= q; i++) scanf("%d%d", &sq[i].first, &sq[i].second);
}
int main() {
    scanf("%d%d%d%d", &n, &q, &p1, &p2);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    init();
    solve();
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
    return 0;
}

By 准备退役旅游的 Cansult