[树状数组]Meaningful Mean

题目描述

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×10⁵
1≤K≤10⁹
1≤ai≤10⁹

 

输入

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.

 

思路：先将a[1~n]都自减k；则区间[l,r]需满足sum[l~r]>=0;即sum[r]>=sum[l-1];    即求有多少对[l,r]使得sum[r]>=sum[l-1];

预处理前缀和得到sum[1~n]; 接着仿照树状数组求逆序数的方法求sum[i]>=sum[j]的对数(1<=j<i;  i作为r,j作为l-1,  则[j+1,i]是一可行区间,此处考虑不到[1,i]这个区间需额外判断)；

AC代码：

#include <iostream>
#include<cstdio>
#include<algorithm>
#define lowbit(x) x&(-x)
typedef long long ll;
using namespace std;

ll a[200010];
int b[200010];
ll c[200010];
int n,k;

struct s{
  ll num;int id;
}sum[200010];

bool cmp(s x,s y){
  if(x.num==y.num) return x.id<y.id;
  return x.num<y.num;
}

bool cmp2(s x,s y){
  return x.id<y.id;
}

void add(int x,int val){
   for(int i=x;i<=n;i+=lowbit(i)){
       c[i]+=val;
   }
}

ll getsum(int x){
   ll ret=0;
   for(int i=x;i>=1;i-=lowbit(i)){
       ret+=c[i];
   }
   return ret;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]-=k,sum[i].num=sum[i-1].num+a[i],sum[i].id=i;
    }
    sort(sum+1,sum+1+n,cmp);
    for(int i=1;i<=n;i++) b[sum[i].id]=i;
    sort(sum+1,sum+1+n,cmp2);
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(sum[i].num>=0) ans++;
        ans+=getsum(b[i]);
        add(b[i],1);
    }
    printf("%lld
",ans);
    return 0;
}