《算法筆記》13.2小節 Problem D 數列-訓練套題T10T3

問題 D: 數列-訓練套題T10T3

題目描述

一個簡單的數列問題：給定一個長度為n的數列，求這樣的三個元素ai, aj, ak的個數，滿足ai < aj > ak，且i < j < k。

輸入

第一行是一個整數n(n <= 50000)。

第二行n個整數ai(0 <= ai <= 32767)。

輸出

一個數，滿足ai < aj > ak (i < j < k)的個數。

樣例輸入

5

1 2 3 4 1
           

樣例輸出

思路

無

代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50010;
#define lowbit(i) ((i)&(-i))
int a[maxn],b[maxn];
int c[maxn];

void update(int x,int v)
{
    for(int i=x;i<maxn;i+=lowbit(i))
    {
        c[i]+=v;
    }
}

int getsum(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        sum+=c[i];
    }
    return sum;
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            b[n-1-i]=a[i];
        }
        int res=0;
        int p[n]={0},q[n]={0};
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++)
        {
            update(a[i],1);
            p[i]=getsum(a[i]-1);
        }
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++)
        {
            update(b[i],1);
            q[i]=getsum(b[i]-1);
        }
        for(int i=0;i<n;i++)
        {
            res+=p[i]*q[i];
        }
        printf("%d\n",res);
    }
    return 0;
}