web analytics

数学,又是数学 归并排序

描述

Liukeke同学(我们敬爱滴亲爱滴可爱滴班长大人)最近又在忙着开班会(真是个工作狂),于是乎,数学学案就被抛到了九霄云外,直到预备铃打完,他才发现那张美丽的雪白的学案,眼看一场血案即将发生,他请你用最快的速度帮他算完第一题:给定一个数串,数串的长度为n,现在将一个子串的每个数字之和定义为该子串的数串和,请你求出数串中有多少个子串的数串和为正数。

输入

第一行一个数n,表示数串的长度。
第二行一共n个数,表示数串中的每个数输出就一个数,表示数串中有多少个子串的数串和为正数。

样例输入

3 8 -9 2

样例输出

3

提示

【数据范围】
30% n ≤ 1000
100% n ≤ 100000
所有数之和在int范围之内

 

分析:

所以归并排序求逆序对。

答案需要开long long int 。

 

Post a Comment

You must be logged in to post a comment.