思路：
此题是求有多少个区间的平均值>=t， 那么可以把每个值-t。如果新的数列的某个区间的和>=0，那么说明这个区间满足条件。
令新数列的前缀和为b[i]，所以求[i, j]区间是否满足条件，即求b[j]-b[i-1]是否>=0，即b[j]>=b[i-1]。
因为j>i>i-1，所以这里即求“伪逆序对”的数量。
扩展知识：
逆序对：i>j a[i]<a[j] 伪逆序对/非逆序对：i>j a[i]>a[j]
方法：归并排序
代码：
1.8/10代码：错误原因：超时
#include <bits/stdc++.h> using namespace std; const long long int N = 1e6 + 10; long long int p = 1e9 + 7; long long int n, t; long long int a[N]; long long int b[N]; int main() { cin >> n >> t; for (long long int i = 1; i <= n; i++) { cin >> a[i]; a[i] -= t; } for (long long int i = 1; i <= n; i++) { b[i] = b[i - 1] + a[i]; } long long int ans = 0; for (long long int i = 1; i <= n; i++) { for (long long int j = 1; j <= i; j++) { if (b[i] - b[j - 1] >= 0) { ans++; } } } cout << ans % p; }
2.10/10代码：升序排列求逆序对，再用总的-逆序对即为非逆序对个数
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e6 + 10; int p = 1e9 + 7; ll n, t; ll a[N], sum[N], q[N]; ll ans = 0; void merge_sort(int l, int r, ll a[]) { if (l >= r) return; int mid = (l + r) >> 1; merge_sort(l, mid, a); merge_sort(mid + 1, r, a); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (a[i] > a[j]) { q[k++] = a[j++]; ans += mid - i + 1; // 升序排列，求逆序数 ans %= p; } else { q[k++] = a[i++]; } } while (i <= mid) q[k++] = a[i++]; while (j <= r) q[k++] = a[j++]; for (i = l, j = 0; i <= r; i++, j++) { a[i] = q[j]; } } int main() { cin >> n >> t; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] -= t; sum[i] = sum[i - 1] + a[i]; } merge_sort(0, n, sum); cout << (n * (n + 1) / 2 - ans) % p; return 0; }
3.10/10代码，直接降序求非逆序对个数
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e6 + 10; int p = 1e9 + 7; ll n, t; ll a[N], sum[N], q[N]; ll ans = 0; void merge_sort(int l, int r, ll a[]) { if (l >= r) return; int mid = (l + r) >> 1; merge_sort(l, mid, a); merge_sort(mid + 1, r, a); int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (a[i] <= a[j]) { q[k++] = a[j++]; ans += mid - i + 1; // 降序排列，求非逆序数 ans %= p; } else { q[k++] = a[i++]; } } while (i <= mid) q[k++] = a[i++]; while (j <= r) q[k++] = a[j++]; for (i = l, j = 0; i <= r; i++, j++) { a[i] = q[j]; } } int main() { cin >> n >> t; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] -= t; sum[i] = sum[i - 1] + a[i]; } merge_sort(0, n, sum); cout << ans % p; return 0; }
