「NOIP模拟赛」弱点

2014年11月4日1,7471

「题目描述」

一队勇士正在向你进攻,每名勇士都有一个战斗值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的话,要求左边比它大的个数和右边比它小的

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

 

说点什么

提醒
avatar
Scott
Scott

请问黄学长,这道题在网上哪里可以评测?