【NOIP模拟赛】弱点

2014年11月4日1,2250

【题目描述】

一队勇士正在向你进攻,每名勇士都有一个战斗值ai。但是这队勇士却有一个致命弱点,如果存在i<j<k使得ai>aj>ak,则会影响他们整体的战斗力。我们将这样的一组(i,j,k)称为这队勇士的一个弱点。请求出这队勇士的弱点数目。

【输入】

输入文件:weakness.in

输入的第一行是一个整数n,表示勇士的数目。

接下来一行包括n个整数,表示每个勇士的战斗值ai。

【输出】

输入文件:weakness.out

输出为一行,包含一个整数。表示这队勇士的弱点数目。

【输入样例】

4

10 8 3 1

【输出样例】

4

【数据范围】

对于30%的数据,3<=n<=100

对于100%的数据,3<=n<=1000000

对于100%的数据,1<=ai<=1000000,每个ai均不相同

题解

枚举i的话,要求左边比它大的个数和右边比它小的

显然树状数组线段树平衡树都可以解决这个问题