Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
斯诺克又称英式台球，是一种流行的台球运动。在球桌上，台面四角以及两长边中心位置各有一个球洞，使用的球分别为1 个白球
，15 个红球和6 个彩球（黄、绿、棕、蓝、粉红、黑）共22个球。击球顺序为一个红球、一个彩球直到红球全部落袋，然后以
黄、绿、棕、蓝、粉红、黑的顺序逐个击球，最后以得分高者为胜。斯诺克的魅力还在于可以打防守球，可以制造一些障碍球使
对方无法击打目标球而被扣分。正是因为这样，斯诺克是一项充满神奇的运动。
现在考虑这样一种新斯诺克，设母球（母球即是白球，用于击打其他球）的标号为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 只有一个数，为“连击”的方案总数。
【数据规模】
Sample Input1
4 3
3 7 2 4
Sample Output1
7
【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u249
【题解】
大概就是说给你一个母球M，然后给你N个球，这N个球的的编号各不相同.然后其并列排成一排，问你
这个球打过去能最多得多少分。。，这个分的平均数要大于M。【原谅我的语言表达能力】
(相当于让你选择连续的序列，序列的和的平均数大于M,问这样的子连续序列的个数);
好的 我们以样例开始讲解
3 7 2 4
我们设一个sum[i]数组，表示1到i求编号加起来的和如sum[2]=10;sum[1]=3;
好的可以看出来符合题意的击球是这样的(sum[i]-sum[j])/(i-j)>M
左边为平均数。右边为要大于的M，
这样以后将其移项一下。
就能得到sum[i]-sum[j]>M*i-M*j
再移动得到sum[i]-M*i>sum[j]-M*j;
然后把sum[i]-M*i看成一个整体v1[i];
sum[j]-M*j看成一个整体V2[j];
则符合题意的击球满足v1[i]>v2[j]且i>j;
把那个v数组取反;
则v1’[i] < v2’[j] 且i>j;
这样就转换成一个求逆序对的模型了；
再加入一个v[0]=0;从0-n这个数组中求逆序对就可以;
如果不加0这个数组
如sum[1]-sum[0]指的就是只击打1的情况如果从1开始则会漏解;
且任何从1开始连续的都会被漏掉;
【完整代码】
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
void rel(LL &r)
{
r = 0;
char t = getchar();
while (!isdigit(t) && t!='-') t = getchar();
LL sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
void rei(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)&&t!='-') t = getchar();
int sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
const int MAXN = 1e5+100;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,-1,1};
const double pi = acos(-1.0);
int n,m;
int v[MAXN],temp[MAXN],sum[MAXN]={0};
LL ans = 0;
void mergesort(int l,int r)
{
if (l==r) return;
int m = (l+r)>>1;
mergesort(l,m);mergesort(m+1,r);
int i = l,j = m+1,k=l;
while (i <= m && j <= r)
if (v[i] > v[j])
ans+=m-i+1,temp[k++] = v[j++];
else
if (v[i] <= v[j])
temp[k++] = v[i++];
while (i <= m) temp[k++] = v[i++];
while (j <= r) temp[k++] = v[j++];
rep1(i,l,r) v[i] = temp[i];
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
rei(n);rei(m);
rep1(i,1,n)
{
int x;
rei(x);
sum[i] = sum[i-1]+x;
v[i] = -sum[i]+i*m;
}
v[0] = 0;
mergesort(0,n);
cout << ans << endl;
return 0;
}