P2717 寒假作业 题解 CDQ分治

寒假作业

传送门

题目背景

zzs 和 zzy 正在被寒假作业折磨，然而他们有答案可以抄啊。

题目描述

他们共有 $n$ 项寒假作业。zzy 给每项寒假作业都定义了一个疲劳值 $a_i$，表示抄这个作业所要花的精力。

zzs 现在想要知道，有多少组连续的寒假作业的疲劳值的平均值不小于 $k$？

简单地说，给定一个长度为 $n$ 的正整数序列 { a i } \{a_i\} { ai​}，求出有多少个连续子序列的平均值不小于 $k$。

输入格式

第一行是两个整数，分别表示序列长度 $n$ 和给定的参数 $k$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

3 2
1
2
3

样例输出 #1

4

提示

样例 1 解释

共有 $6$ 个连续的子序列，分别是 $(1)$、$(2)$、$(3)$、$(1,2)$、$(2,3)$、$(1,2,3)$，平均值分别为 $1$、$2$、$3$、$1.5$、$2.5$、$2$，其中平均值不小于 $2$ 的共有 $4$ 个。

数据规模与约定

• 对于 $20\%$ 的数据，保证 $n\le 100$。
• 对于 $50\%$ 的数据，保证 $n\le 5000$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$1\le a_i,k\le 10^4$。

$以上来自洛谷$

解题思路

题目看不懂？确实题面可以转化为：求平均值大于等于k的区间个数。是不是想用 $CDQ$ 了？我偏不用。

考虑暴力

枚举每个区间的右端点，枚举相应的区间。时间复杂度 $O(n^2)$。

优化

对于平均值的处理，可以把 $a_i-k$，这样问题就转换为求出区间和大于等于0的区间个数
枚举右端点之后，考虑怎么快速求出左边区间和大于等于 $0$ 的个数。
定义 $tot$ 表示当前以 $i$ 为右端点的前缀和，用一个vector<int> sum维护当前右端点对应的所有左端点加 $tot$ 表示某段区间和。这样每次只要求出 $sum+tot\ge 0$ 的个数，很容易想到二分，不可以手打，但有函数可以直接用。用lower__bound与insert保证插入后vector有序。考虑插入对于当前位置 $j$，$j$ 到 $i$ 的区间和，表示为 $Su{m}_i-Su{m}_{j-1}$。而 $Su{m}_{j-1}$ 就是当前枚举到j还没有加上 $a_j$ 的 $tot$。时间复杂度 $O(n\times \sqrt{n})$，这不就过了吗。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 4e5 + 5;
int n, k, a[Maxn];
vector<int> sum;
int tot;
int ans;
inline void work() {
   
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
   
		cin >> a[i];
		a[i] -= k;
	}
	int tmp;
	for (int i = 1; i <= n; i++) {
   
		sum.insert(lower_bound(sum.begin(), sum.end(), -tot), -tot);
		tot += a[i];
		tmp = sum.end() - lower_bound(sum.begin(), sum.end(), -tot);
		ans += tmp;
	}
	cout << ans << endl;
}
signed main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}
//CDQ?

什么？你还想写 $CDQ$？