图腾计数 - c++编程基础

Description

Ciocio 最近参观了楼兰图腾。图腾的所在地有一排N个柱子，N个柱子的高度恰好为一个1到N的排列，而楼兰图腾就隐藏在这些柱子中。

由于Ciocio弱爆了，他只知道图腾由3个柱子组成，这三个柱子组成了下凸或上凸的图形（>.<），所谓下凸，设三个柱子的高度从左到右依次为 1， 2， 3，那么 1> 2， 2< 3，上凸则满足 1< 2， 2> 3。

现在Ciocio也找不到图腾具体是哪三个柱子，他只想知道满足这两个形状的柱子有几组。

Input

第一行一个数N

接下来一行N个数，依次表示每个柱子的高度

Output

一行两个数，表示下凸形状的数量和上凸形状的数量，用空格隔开

Sample Input

1 5 3 2 4

Sample Output

3 4

Hint

n≤200000

【分析】

记i左边比他大的个数为bigl，右边比他大的个数为bigr。同理，记i左边比他小的个数为smal，右边比他小的个数为smar。

那么显然对于下凸柱子的个数，就为sum(bigl[i]*bigr[i])。上凸柱子的个数，就为sum(smal[i]*smar[i])；

这一步是很容易想到的，但是难就难在如何求这四个数组。我们可以用树状数组来完成这一步。树状数组的下标表示每个i的高度。我们顺序（输入顺序）依次插入每个i（即插入位置是h[i]），插入时，那么树状数组中的h[i]的前缀和，就一定是他的smal。

因为h[i]的前缀和求出来的个数，一定是在i之前插入的，即在i左边的。而且由于树状数组的下标为每个i的高度，所以在他左边的一定是比他矮的。注意到柱子高度是1到N的一个排列，所以不需离散化。同理可求出其他三个数组。

再回过头来看这道题，很巧妙地应用了树状数组来维护动态的操作。

【代码】

#include




  
#include  
#include  
#include  
#include  
#include  
#include  
#define _lowbit(x) (x&(-x))         //定义_lowbit   
using namespace std;  
int N,bigl[200005],bigr[200005],smal[200005],smar[200005];  
int c[200005],h[200005];  
void _in(int &x)  
{  
    char t=getchar();  
    while(t<'0'||'9'