洛谷P3722 [AH2017/HNOI2017]影魔(线段树)

题意

题目链接

sol

题解好神仙啊qwq。

一般看到这种考虑最大值的贡献的题目不难想到单调数据结构

对于本题而言，我们可以预处理出每个位置左边第一个比他大的位置\(l_i\)以及右边第一个比他大的位置\(r_i\)

那么\((l_i, r_i)\)会产生\(p1\)的贡献

\([l_i + 1, i - 1]\)和\(r_i\)会产生\(p2\)的贡献

\([i + 1, r_i - 1]\)和\(l_i\)会产生\(p2\)的贡献

这样我们直接上区间加线段树就能统计到每个点的贡献了。

然后统计答案非常神仙，我们把询问拆开，当枚举到\(l - 1\)时，记此时\([l,r]\)的\(sum\)为\(s1\)，当枚举到\(r\)时，记此时\([l, r]\)的\(sum\)为s2，那么该询问的答案为\(s2 - s1\)

复杂度：\(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;
}