看错题
不知道为什么,式子到我手上就变成了:$\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$ 的贡献。分为两部分:
- $a_i$ 在 $i=j$ 的时候取到自己:$(i - l_i) \times (r_i - i) \times (n - r_i + 1) \times a_i$
- 在 $i \neq j$ 的时候自己和别的区间取到 $a_i$ 的贡献,那么 $a_i$ 会贡献一段前缀,并且因为前缀也会重复计算多次,那么就是每次乘一个前缀和,即:$(i - l_i) \times (s_{r_i - i}) \times a_i$
Idea
- 看清楚题目要求(真的感觉印度人写的英文看不懂,可能这就是“平行外语”吧)
- 考虑对每个元素单独计算其贡献。
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;
}
2 条评论
李欣泽,为什么你的博客在每个初二那边的收藏夹里啊
毕竟我写的有趣