CodeChef SUMSUB Subarray Sum

博主： tony102
发布时间：2021 年 11 月 17 日
2586 次浏览
2 条评论
599字数
分类：题解

[Link](https://www.codechef.com/START16C/problems/SUMSUB)

## 看错题

不知道为什么，式子到我手上就变成了：$\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 了。

```cpp
#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

```cpp
#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];

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;
}
```

最后修改：2021 年 11 月 17 日

如果觉得我的文章对你有用，请随意赞赏

2 条评论

yzhx
November 18th, 2021 at 09:20 pm

李欣泽，为什么你的博客在每个初二那边的收藏夹里啊

回复
1. tony102
  November 19th, 2021 at 12:44 am
  
  @yzhx
  
  毕竟我写的有趣
  
  回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了
Yanws
牢师求更新

CodeChef SUMSUB Subarray Sum

tony102 • 2021 年 11 月 17 日

[Link](https://www.codechef.com/START16C/problems/SUMSUB)

## 看错题

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

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

```cpp
#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];

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

## Sol

## Idea

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

## Code

```cpp
#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];

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;
}
```

CodeChef SUMSUB Subarray Sum

2 条评论

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

Multi-View Silhouette and Depth Decomposition for High Resolution 3D Object Representation

ARC125B Squares

20211115 旋转吧 (maware)

Contest: AtCoder Beginner Contest 226

2021年暑假训练总结2

CodeChef SUMSUB Subarray Sum

2 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

CodeChef SUMSUB Subarray Sum

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款