Link

看错题

不知道为什么，式子到我手上就变成了：$\sum\limits_{i=1}^{n} \sum\limits_{j=i}^{n} \max\{a_k |l \leq k \leq r\}$

就随便写一个线段树维护最大值及其下标，每次询问 $\geq a_i$ 的位置，不存在即为 $1$ 或 $n$，影响的区间就是 $len = r - l + 1, \frac{len \times (len - 1)}{2}$ 个。统计每个 $a_i$ 的贡献就行了。

这可能是个普及难度的线段树练习题。是我低估 CC 了。

#include <bits/stdc++.h>
using namespace std;

typedef pair < int, int > PII;
typedef long long LL;
const int SIZE = 2e5 + 5, mod = 1e9 + 7;

int q, n;
int a[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

namespace segT {
    #define lson(p) (p << 1)
    #define rson(p) (p << 1 | 1)
    PII t[SIZE << 2];
    PII operator + (PII a, PII b) { 
        return (PII) {max(a.first, b.first), a.first > b.first ? a.second : b.second}; 
    }
    void build(int p = 1, int l = 1, int r = n) {
        t[p] = {-mod, l};
        if (l == r) return t[p] = {a[l], l}, void();
        int mid = (l + r) >> 1;
        build(lson(p), l, mid), build(rson(p), mid + 1, r);
        t[p] = t[lson(p)] + t[rson(p)];
    }
    PII query(int ql, int qr, int k, int p = 1, int l = 1, int r = n) {
        PII ans = {-mod, l};
        if (ql <= l && r <= qr) {
            if (t[p].first > k) return t[p];
            else return ans;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid) ans = ans + query(ql, qr, k, lson(p), l, mid);
        if (qr > mid) ans = ans + query(ql, qr, k, rson(p), mid + 1, r);
        return ans;
    }
    void debug(int p = 1, int l = 1, int r = n) {
        printf("[%d %d]: (%d %d)\n", l, r, t[p].first, t[p].second);
        if (l == r) return; 
        int mid = (l + r) / 2;
        debug(lson(p), l, mid), debug(rson(p), mid + 1, r);
    }
} using segT::build; using segT::query;

void sol() {
    n = read(); LL ans = 0;
    for (int i = 1; i <= n; ++ i) a[i] = read();
    build();
    for (int i = 1; i <= n; ++ i) {
        PII xl = query(1, max(1, i - 1), a[i]), xr = query(min(i + 1, n), n, a[i]);
        // printf("xl:(%d %d) xr:(%d %d) a[i]:%d\n", xl.first, xl.second, xr.first, xr.second, a[i]);
        int l = min(xl.second + 1, i), r = max(i, xr.second - 1), len = r - l + 1;
        if (xl.first < a[i]) l = 1;
        if (xr.first < a[i]) r = n;
        len = r - l + 1;
        int cnt = (len == 1 ? 1 : (len * (len - 1) / 2));
        // printf("l:%d r:%d cnt:%d\n", l, r, cnt);
        ans = (ans + 1ll * cnt * a[i] % mod) % mod;
    }
    printf("%lld\n", ans);
}

int main() {
    freopen("code.in", "r", stdin);
    q = read();
    while (q --) sol();
    return 0;
}

Sol

首先可以预处理出 $i$ 左右两边的区间第一个 $> a_i$ 的数的位置。如果没有说明 $a_i$ 是这一段前缀或者后缀的最大值，直接设成 $0$ 或 $n+1$ 即可。记这两个端点分别为：$l_i,r_i$。然后计算 $a_i$ 的贡献。分为两部分：

1. $a_i$ 在 $i=j$ 的时候取到自己：$(i - l_i) \times (r_i - i) \times (n - r_i + 1) \times a_i$
2. 在 $i \neq j$ 的时候自己和别的区间取到 $a_i$ 的贡献，那么 $a_i$ 会贡献一段前缀，并且因为前缀也会重复计算多次，那么就是每次乘一个前缀和，即：$(i - l_i) \times (s_{r_i - i}) \times a_i$

Idea

1. 看清楚题目要求（真的感觉印度人写的英文看不懂，可能这就是“平行外语”吧）
2. 考虑对每个元素单独计算其贡献。

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 2e5 + 5, mod = 1e9 + 7;

int q, n;
int a[SIZE], l[SIZE], r[SIZE], s[SIZE], stk[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

void sol() {
    n = read(); int top = 0; LL ans = 0;
    for (int i = 1; i <= n; ++ i) a[i] = read();
    for (int i = 1; i <= n; ++ i) {
        while (top && a[stk[top]] < a[i]) -- top;
        if (top) l[i] = stk[top];
        else l[i] = 0;
        stk[++ top] = i;
    }
    top = 0;
    for (int i = n; i; -- i) {
        while (top && a[stk[top]] <= a[i]) -- top;
        if (top) r[i] = stk[top];
        else r[i] = n + 1;
        stk[++ top] = i;
    }
    for (int i = 1; i <= n; ++ i) {
        int len = 1ll * (i - l[i]) * (s[r[i] - i]) % mod;
        ans = (ans + 1ll * len * a[i] % mod) % mod;
        len = 1ll * (i - l[i]) * (r[i] - i) % mod * (n - r[i] + 1) % mod;
        ans = (ans + 1ll * len * a[i] % mod) % mod;
    }
    printf("%lld\n", ans % mod);
}

int main() {
    freopen("code.in", "r", stdin);
    q = read();
    for (int i = 1; i <= 2e5; ++ i) s[i] = 1ll * (s[i - 1] + i) % mod;
    while (q --) sol();
    return 0;
}