OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题1291--逆序对求和

1291: 逆序对求和

时间限制: 1 Sec  内存限制: 128 MB
提交: 88  解决: 44
[提交] [状态] [讨论版] [命题人:]

题目描述

给你一个长度为n的序列，我们容易知道这个序列的逆序对个数，但是现在将问题转化，整个序列共有n*(n+1)/2个子区间，
(子区间即为序列中连续的区间)，需要你求出每个子区间的逆序对数目，然后加起来输出其总和。
由于答案过大，需要对1000000007取模(mod=1e9+7)

输入

首先第一行一个数n，表示序列的长度 （1<=n<=200000）
接下来一行n个数，ai表示每个位置上的值 （1<=ai<=1000000000）

输出

输出一个整数，表示所有子区间逆序对数目的总和。

样例输入 Copy 

8
0 5 3 1 1 9 9 4

样例输出 Copy 

72

来源/分类

 
[提交] [状态]