P2717 寒假作业（CDQ 分治）
P2717 寒假作业
题目传送门
- P2717 寒假作业
- 题目背景
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 样例 1 解释
- 数据规模与约定
- 思路
- code
题目背景
zzs 和 zzy 正在被寒假作业折磨，然而他们有答案可以抄啊。
题目描述
他们共有 \(n\) 项寒假作业。zzy 给每项寒假作业都定义了一个疲劳值 \(a\)，表示抄这个作业所要花的精力。
zzs 现在想要知道，有多少组连续的寒假作业的疲劳值的平均值不小于 \(k\)？
简单地说，给定一个长度为 \(n\) 的正整数序列 \(\{a_i\}\)，求出有多少个连续子序列的平均值不小于 \(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 \leq 100\)。
- 对于 \(50\%\) 的数据，保证 \(n \leq 5000\)。
- 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)，\(1 \leq a_i,k \leq 10^4\)。
思路
我们把题意简化一下，就是求一个区间 \([l , r]\) 满足 \(\frac{\sum_{i = l}^r}{r - l + 1} \ge k\) 的数量。
我们可以推理一下：
首先我们如果把 \(a\) 数组全部减 \(k\) 那么上述式子就变成了：\(\frac {\sum_{i = l}^r}{r - l + 1} \ge 0\)
即：\(\sum_{i = l}^r \ge 0\)
设 \(s\) 表示 \(a\) 数组的前缀和。
带入上述式子：\(s_r - s_{l - 1} \ge 0\)
到这里题目就已经转换成了：求 \(i , j(1 \leq i < j \leq n)\) 满足 : \(s_j \ge s_i\) 的数量
也就是求 \(s\) 数组的顺序对的数量：
可以用归并排序或者树状数组来求。
不会归并排序的可以看这个
code
#include <bits/stdc++.h>
#define LL long long
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const int N = 1e5 + 5;
int a[N] , s[N] , n , k;
LL ans;
int read () {
int val = 0 , fu = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') {
if (ch == '-') fu = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
val = val * 10 + (ch - '0');
ch = getchar ();
}
return val * fu;
}
void gb(int l , int r) {
if (l == r) return;
else {
int mid = l + r >> 1;
gb (l , mid);
gb (mid + 1 , r);
fu (i , l , r) a[i] = s[i];
int i = l , j = mid + 1 , sum = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
ans += r - j + 1;
s[sum ++] = a[i ++];
}
else
s[sum ++] = a[j ++];
}
while (i <= mid) s[sum ++] = a[i ++];
while (j <= r) s[sum ++] = a[j ++];
}
}
int main () {
n = read () , k = read ();
fu (i , 1 , n) {
a[i] = read ();
a[i] -= k;
}
fu (i , 1 , n) s[i] = s[i - 1] + a[i];
fu (i , 1 , n) ans += (s[i] >= 0);
gb (1 , n);
printf ("%lld" , ans);
return 0;
}