问题1592--数列（逆序对问题）

1592: 数列（逆序对问题）

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

题目描述

一个简单的数列问题：给定一个长度为n的数列，求这样的三个元素ai, aj, ak的个数，满足ai < aj > ak，且i < j < k。

输入

第一行是一个整数n(n ≤ 50000)。
接下来n行，每行一个元素ai(0≤ ai≤32767)。

输出

一个数，满足ai < aj > ak (i < j < k)的个数。

样例输入 Copy 

5
1
2
3
4
1

样例输出 Copy 

6

提示

【数据及时间和空间限制】
对于30%的输入数据，有n≤200;
对于80%的输入数据，有n≤10000。
时间限制为1秒，空间限制为256MB。

来源/分类

树状数组 线段树 
[提交] [状态]