题目描述
You are given an integer sequence of length N, a= {a1,a2,…,aN}, and an integer K.
a has N(N+1)⁄2 non-empty contiguous subsequences, {al,al+1,…,ar} (1≤l≤r≤N). Among them, how many have an arithmetic mean that is greater than or equal to K?
Constraints
All input values are integers.
1≤N≤2×105
1≤K≤109
1≤ai≤109
输入
Input is given from Standard Input in the following format:
N K
a1
a2
:
aN
输出
Print the number of the non-empty contiguous subsequences with an arithmetic mean that is greater than or equal to K.
样例输入
3 6
7
5
7
样例输出
5
提示
All the non-empty contiguous subsequences of a are listed below:
{a1} = {7}
{a1,a2} = {7,5}
{a1,a2,a3} = {7,5,7}
{a2} = {5}
{a2,a3} = {5,7}
{a3} = {7}
Their means are 7, 6, 19⁄3, 5, 6 and 7, respectively, and five among them are 6 or greater. Note that {a1} and {a3} are indistinguishable by the values of their elements, but we count them individually.
首先对于所有数减去k，这样就不用除(r-l+1), 然后我们发现所求的就是有多少对l,r，使得sum[r]-sum[l-1] >= 0, sum是减去k之后的序列的前缀和
用树状数组对sum求有多少个顺序对，多加一个0这个数，代表从sum[r]-sum[0]对答案的贡献。
由于sum[i]可能很大，所以需要离散化 用unique
#include <bits/stdc++.h>
#define ll long long
const int mod=1e9+;
const int maxn=2e5+;
using namespace std;
//int s[maxn];
ll sum[maxn],t[maxn];
ll tree[maxn];
int nn,m;
void add(int x)
{
while(x<=nn)//nn为上限，要大于离散化后的最大的数字，
{
tree[x]++;
x+=x&-x;//向上更新，树状数组核心代码。此处就不解释了，不会的先学树状数组。
}
}
ll query(int x)
{
ll num=;
while(x)
{
num+=tree[x];
x-=x&-x;//向下求和
}
return num;
}
int main()
{
int n,k,a;
scanf("%d %d",&n,&k);
nn=n+;
for(int i=;i<=n;i++){
scanf("%d",&a);
sum[i]=t[i]=sum[i-]+a-k;
}
sort(t,t+n+);
m=unique(t,t+n+)-t;
for(int i=;i<=n;i++){
sum[i]=lower_bound(t,t+m+,sum[i])-t+;
}
ll ans=;
for(int i=;i<=n;i++){
ans+=query(sum[i]);
add(sum[i]);
}
printf("%lld\n",ans);
return ;
}
