P2717 寒假作业 CDQ
寒假作业
传送门
题目背景
zzs 和 zzy 正在被寒假作业折磨，然而他们有答案可以抄啊。
题目描述
他们共有 n n n 项寒假作业。zzy 给每项寒假作业都定义了一个疲劳值 a i a_i ai，表示抄这个作业所要花的精力。
zzs 现在想要知道，有多少组连续的寒假作业的疲劳值的平均值不小于 k k k？
简单地说，给定一个长度为 n n n 的正整数序列 { a i } \{a_i\} {ai}，求出有多少个连续子序列的平均值不小于 k k k。
输入格式
第一行是两个整数，分别表示序列长度 n n n 和给定的参数 k k k。
第二行有 n n n 个整数，第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
3 2
1
2
3
样例输出 #1
4
提示
样例 1 解释
共有 6 6 6 个连续的子序列，分别是 ( 1 ) (1) (1)、 ( 2 ) (2) (2)、 ( 3 ) (3) (3)、 ( 1 , 2 ) (1,2) (1,2)、 ( 2 , 3 ) (2,3) (2,3)、 ( 1 , 2 , 3 ) (1,2,3) (1,2,3)，平均值分别为 1 1 1、 2 2 2、 3 3 3、 1.5 1.5 1.5、 2.5 2.5 2.5、 2 2 2，其中平均值不小于 2 2 2 的共有 4 4 4 个。
数据规模与约定
- 对于 20 % 20\% 20% 的数据，保证 n ≤ 100 n \leq 100 n≤100。
- 对于 50 % 50\% 50% 的数据，保证 n ≤ 5000 n \leq 5000 n≤5000。
- 对于 100 % 100\% 100% 的数据，保证 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105， 1 ≤ a i , k ≤ 1 0 4 1 \leq a_i,k \leq 10^4 1≤ai,k≤104。
以上来自洛谷 以上来自洛谷 以上来自洛谷
解题思路
题目看不懂？确实题面可以转化为：求平均值大于等于k的区间个数。是不是想用 C D Q CDQ CDQ 了？我偏不用。
考虑暴力
枚举每个区间的右端点，枚举相应的区间。时间复杂度 O ( n 2 ) O(n^2) O(n2)。
优化
对于平均值的处理，可以把 a i − k a_i-k ai−k，这样问题就转换为求出区间和大于等于0的区间个数
枚举右端点之后，考虑怎么快速求出左边区间和大于等于 0 0 0 的个数。
定义 t o t tot tot 表示当前以 i i i 为右端点的前缀和，用一个vector<int> sum维护当前右端点对应的所有左端点加 t o t tot tot 表示某段区间和。这样每次只要求出 s u m + t o t ≥ 0 sum+tot\ge 0 sum+tot≥0 的个数，很容易想到二分，不可以手打，但有函数可以直接用。用lower__bound与insert保证插入后vector有序。考虑插入对于当前位置 j j j， j j j 到 i i i 的区间和，表示为 S u m i − S u m j − 1 Sum_i-Sum_{j-1} Sumi−Sumj−1。而 S u m j − 1 Sum_{j-1} Sumj−1 就是当前枚举到j还没有加上 a j a_j aj 的 t o t tot tot。时间复杂度 O ( n × n ) O(n\times \sqrt n) O(n×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?
什么？你还想写 C D Q CDQ CDQ？