Meaningful Mean
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
输入
N K
a1
a2
:
aN
输出
样例输入
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.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct poi{ll sum,pos;}a[200010];
ll n,k,ans,cnt,tree[200010],lisan[200010];
void read(ll &k)
{
k=0;int f=1;char c=getchar();
while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
k*=f;
}
bool cmp(poi a,poi b){return a.sum<b.sum;}
int lowbit(int x){return x&-x;}
void add(int x,int delta)
{
for(int i=x;i<=cnt;i+=lowbit(i))
tree[i]+=delta;
}
int sum(int x)
{
int s=0;
for(int i=x;i>=1;i-=lowbit(i))
s+=tree[i];
return s;
}
int main()
{
read(n);read(k);
for(int i=1;i<=n;i++)read(a[i].sum),a[i].sum-=k;
for(int i=1;i<=n;i++)a[i].sum+=a[i-1].sum,a[i].pos=i;
sort(a,a+1+n,cmp);
for(int i=0;i<=n;i++)
{
if(a[i].sum!=a[i-1].sum||i==0)cnt++;
lisan[a[i].pos]=cnt;
}
for(int i=n;i>=0;i--)
{
ans+=sum(cnt)-sum(lisan[i]-1);
add(lisan[i],1);
}
printf("%lld\n",ans);
}
最新文章
- thinkphp3.2.3之自动完成的实现
- KMP快速字符串匹配
- C_中使用SendMessage
- Swift中的字典
- Bzoj 2120: 数颜色 &;&; 2453: 维护队列 莫队,分块,bitset
- jquery实现点击改变背景色,点击其他恢复原来背景色,被点击的改变背景色
- Fedora25
- poj 1008
- [SQL]LeetCode176. 第二高的薪水 | Second Highest Salary
- 小tips:node起一个简单服务,打开本地项目或文件浏览
- linux运行进程实时监控pidstat详解
- [Cubieboard] 安装 Lubuntu server for SDCard
- scp拷贝文件报错-bash: scp: command not found
- ls: Call From hdoop2/192.168.18.87 to hdoop2:8020 failed on connection exception: java.net.ConnectException: 拒绝连接; For more details see
- 如何分析Java虚拟机死锁
- python基础数据类型3
- Java网络编程-HTTP协议
- apt 查询软件
- django 1.10以上版本,引入js
- Swing 添加超链接 打开页面