2021杭电多校4 E Didn't I Say to Make My Abilities Average in the Next Life?!

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=6989

简要题意：给定一个长度为 $n$​ 的序列 $a$​，有 $m$​ 次询问，每次给定询问区间 $[l,r]$​，求 $\sum_{l\le x\le y\le r} \frac{\frac{max~a_{x\cdots y}+min~a_{l\cdots r}}{2}}{\frac{n(n+1)}{2}}$，可以离线​

$n,m\le 3\times 10^5$

Solution

首先我们考虑将询问离线，按照线段树的最经典做法，右端点增大，用线段树维护左端点

现在我们来考虑如何在右端点递增的时候维护这个东西

首先我们将询问拆成求最大值和最小值，我们以最大值为例，然后我们考虑对于每个点求其作为最大值的范围，对于 $i$​ 其范围为 $l_i,r_i$​，那么它的贡献为 $a_i(i-l_i+1)(r_i-i+1)$​

那么在右端点递增的时候，不妨设其为 $i$，我们要维护两种东西，一是 $r_ji$ 的 $j$，第一种在 $i$​ 继续增大的时候贡献已经不会改变了，另一种会继续改变

我们考虑单调栈的过程，$r_ji$ 的点是加入 $i$ 之后仍在单调栈中的点

对于 $r_j<i$​ 的点，我们只需要将其删除的时候，将 $l_j$​ 到 $j$​ 增加一个等差数列，$1$ 到 $l_j-1$ 都加上 $l_j$ 应该增加的数

而对于 $r_j<i$ 的点，单调栈中的这些点将区间分成了若干段，每一段的贡献都是一个等差数列，对于等差数列，我们考虑在求值的时候，不做单点而是做后缀查询，这样可以将等差数列推平，然后我们发现每一段的贡献都相同

大概就是下图的样子

我们可以考虑这样维护，每个点维护 $a\times b$，其中 $a$ 表示这一段最大值，$b$ 表示应该加多少次，其实就是 $i$ 每递增一次，所有的 $b$ 都要加 $1$​，然后 $a$ 每次只有区间赋值，$b$ 只有区间加，还是比较好维护的

大概就是这样

#include <iostream>
#include <vector>
#define maxn 200010
#define INF 1000000001
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

inline int madd(int x, int y) { return (x += y) >= p ? x - p : x; }

int n, m, a[maxn];

struct Seg1 {
#define lc (i << 1)
#define rc (i << 1 | 1)
    struct node {
        int v, add;
    } T[maxn * 4];
    void build(int i, int l, int r) {
        T[i] = { 0, 0 };
        if (l == r) return ;
        int m = l + r >> 1;
        build(lc, l, m); build(rc, m + 1, r);
    }

    void update(int i, int l, int r, int L, int R, int v) {
        if (l > R || r < L) return ;
        T[i].v = madd(T[i].v, 1ll * (min(r, R) - max(L, l) + 1) * v % p);
        if (L <= l && r <= R) return T[i].add = madd(T[i].add, v), void();
        int m = l + r >> 1;
        update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    }

    int query(int i, int l, int r, int L, int R, int add = 0) {
        if (l > R || r < L) return 0;
        if (L <= l && r <= R) return (T[i].v + 1ll * (r - l + 1) * add) % p;
        int m = l + r >> 1;
        return madd(query(lc, l, m, L, R, madd(T[i].add, add)), query(rc, m + 1, r, L, R, madd(T[i].add, add)));
    }
} T1;

struct Seg2 {
    struct node {
        int v, a, b;
        int covera, addb;
    } T[maxn * 4];
    inline void maintain(int i) {
        T[i].v = madd(T[lc].v, T[rc].v);
        T[i].a = madd(T[lc].a, T[rc].a);
        T[i].b = madd(T[lc].b, T[rc].b);
    }

    void build(int i, int l, int r) {
        T[i] = { 0, 0, 0, 0, 0 };
        if (l == r) return ;
        int m = l + r >> 1;
        build(lc, l, m); build(rc, m + 1, r);
    }

    inline void Update_covera(int i, int l, int r, int v) {
        T[i].v = 1ll * v * T[i].b % p;
        T[i].a = 1ll * (r - l + 1) * v % p;
        T[i].covera = v;
    }

    inline void Update_addb(int i, int l, int r, int v) {
        T[i].v = madd(T[i].v, 1ll * v * T[i].a % p);
        T[i].b = madd(T[i].b, 1ll * v * (r - l + 1) % p);
        T[i].addb = madd(T[i].addb, v);
    }

    inline void pushdown(int i, int l, int r) {
        int m = l + r >> 1, &covera = T[i].covera, &addb = T[i].addb;
        if (covera) Update_covera(lc, l, m, covera), Update_covera(rc, m + 1, r, covera);
        if (addb) Update_addb(lc, l, m, addb), Update_addb(rc, m + 1, r, addb);
        covera = addb = 0;
    }

    void update_covera(int i, int l, int r, int L, int R, int v) {
        if (l > R || r < L) return ;
        if (L <= l && r <= R) return Update_covera(i, l, r, v);
        int m = l + r >> 1; pushdown(i, l, r); 
        update_covera(lc, l, m, L, R, v); update_covera(rc, m + 1, r, L, R, v);
        maintain(i); 
    }

    void update_addb(int i, int l, int r, int L, int R, int v) {
        if (l > R || r < L) return ;
        if (L <= l && r <= R) return Update_addb(i, l, r, v);
        int m = l + r >> 1; pushdown(i, l, r); 
        update_addb(lc, l, m, L, R, v); update_addb(rc, m + 1, r, L, R, v);
        maintain(i); 
    }

    int query(int i, int l, int r, int L, int R) {
        if (l > R || r < L) return 0;
        if (L <= l && r <= R) return T[i].v;
        int m = l + r >> 1; pushdown(i, l, r);
        return madd(query(lc, l, m, L, R), query(rc, m + 1, r, L, R));
    }
} T2;

vector<pair<int, int>> A[maxn];

int st[maxn], top, ans[maxn];
void solve(int type) {
    st[top = 1] = 0; a[0] = type > 0 ? INF : 0;
    T1.build(1, 1, n); T2.build(1, 1, n); 
    for (int i = 1; i <= n; ++i) {
        while (top && a[i] >= a[st[top]]) {
            T1.update(1, 1, n, st[top - 1] + 1, st[top], 1ll * type * a[st[top]] * (i - st[top]) % p);
            T2.update_addb(1, 1, n, st[top - 1] + 1, st[top], p - i + st[top]);
            --top;
        }
        T2.update_covera(1, 1, n, st[top] + 1, i, type * a[i]);
        T2.update_addb(1, 1, n, 1, i, 1);
        st[++top] = i;
        for (auto t : A[i]) {
            ans[t.second] = madd(ans[t.second], T1.query(1, 1, n, t.first, i));
            ans[t.second] = madd(ans[t.second], T2.query(1, 1, n, t.first, i));
        }
    }
}

int inv[maxn];
void work() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) A[i].clear();
    for (int i = 1; i <= m; ++i) ans[i] = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        A[y].emplace_back(x, i);
        inv[i] = pow_mod(1ll * (y - x + 1) * (y - x + 2) % p, p - 2);
    }
    solve(1);
    for (int i = 1; i <= n; ++i) a[i] = -a[i];
    solve(-1);
    for (int i = 1; i <= m; ++i) cout << 1ll * ans[i] * inv[i] % p << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}