新斯诺克( ( ( sheeta.pas/c/cpp sheeta.pas/c/cpp sheeta.pas/c/cpp ) ) )
【问题描述】
斯 诺克又称英式台球，是一种 流行的 台球运动 。在球桌上 ，台面四角以及两长边中心位置各 有一个球洞，使用的球分 别 为 1 个白球， 15 个红球和 6 个彩球（黄、绿、棕、蓝、粉红、黑）共 2 2个球。击球顺序为一个红球、一个彩球直到红球全部落袋，然后以黄、绿、棕、蓝、粉红、黑的 顺序逐个击球，最后以得分高者为胜。 斯诺克的魅力还在于可以打防守球，可以制造一些障碍球使 对方无法击打目标球而被扣分。正是因为这样，斯诺克是一项充满神奇的运动。
现在考虑这样一种新斯诺克，设母球（母球即是白球，用于击打其他球）的标号为 M ，台面 上有 N 个红球排成一排，每一个红球都有一个标号，他们的标号代表了他们的分数。
现在用母球击打这些红球，一杆击打，如果母球接触到红球，就称为 “ K 到红球 ” 。我们假设 ，一次可以击打任意多相邻连续的红球，也可以只击打一个球。
并且红球既不会落袋，也不会相互发生碰撞，而只是停留在原处。每次击打时候，要想 “ K 到红球 ” ，至少要击打一个红球，如果想一次击打多个红球，那么击打的红球必须是依次连续排列的 。如果一次 “ K 到红球 ” 所有红球的标号之和的平均数大于母球的标号 M ，就获得了一个 “ 连 击 ” 。现在请你计算总共能有多少种 “ 连击 ” 方案。
注意：如果当前有标号为 1 、 2 、 3 的三种红球，母球标号为 0 ，有如下 6 种获得 “ 连击 ” 方案：（ 1 ）、（ 2 ）、（ 3 ）、（ 1 ， 2 ）、（ 2 ， 3 ）、（ 1 ， 2 ， 3 ）
【输入文件】
输入文件 sheeta.in 共有两行，第一行是 N ， M (N<=100000 ， M<=10000) ， N 表示台 面上一共有 N 个红球， M 表示母球的标号。
第二行是 N 个正整数，依次表示台面上 N 个红球的标号，所有标号均不超过 10000 。
【输出文件】
输出文件 sheeta.out 只有一个数，为 “ 连击 ” 的方案 总 数 。
【输入样例】
4 3
3 7 2 4
【输出样例】
7

说白了就一句话的事情：在一个长度为N序列中，问能取几个连续的子序列，使得每一个子序列的数之和的平均数>M。

更蛋疼的是它的解法：

(sum[j]-sum[i])/(j-i) > m 其中j>i
即sum[j]-sum[i] > j*m -i*m
即sum[j]-j*m > sum[i]-i*m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("sheeta.in");
ofstream fout("sheeta.out");

unsigned long long result;
int n, m, a[100001], b[100001];
void merge(int l, int r)
{
  int i = l, r1 = (l+r)/2;
  int j = r1+1, r2 = r;
  int k = l-1;
  while (k<=r)
  {
      if (j>r2 || i<=r1 && a[i]>=a[j])
          b[++k] = a[i++];
      else
      {
          b[++k] = a[j++];
          result += r1-i+1;
      }
  }
  for (size_t i = l; i <= r; ++i)
      a[i] = b[i];
}
void merge_sort(int l, int r)
{
  if (l == r)
      return;
  int mid = (l+r)/2;
  merge_sort(l, mid);
  merge_sort(mid+1, r);
  merge(l, r);
}
int main()
{
  fin >> n >> m;
  int sum = 0;
  for (size_t i = 1; i <= n; ++i)
  {
      fin >> a[i];
      sum += a[i];
      a[i] = sum-i*m;
  }
  merge_sort(0, n);
  fout << result;
}