cdoj 841 休生伤杜景死惊开 逆序数/树状数组

休生伤杜景死惊开

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

陆伯言军陷八卦阵之中，分明只是一条直路，却怎的也走不到尽头。阵中尽是石堆，以某一石堆为参考，无论向走还是向右，总是会回到出发的石堆,最后幸得一黄姓老翁带路才得脱出。

陆伯言逃离八卦阵后，来到山顶观察此阵，记从左往右第i堆石堆的高度为Ai，发现任何两堆较矮的石堆都能和它们之间的一座较高的石堆形成"八卦锁"，将其中之人牢牢锁住，无从逃脱。

根据石堆的情况，陆伯言大致计算了“八卦锁”的数量（即 Ai<Aj>Ak,i<j<k 的组合数），不禁心中一惊,对孔明惊为天人，遂放弃追击，收兵回吴。

“有劳岳父了。” “为何将其放走？” “...一表人才，何必浪费于此。”
Input

第一行一个整数n，表示石堆堆数。

接下来一行，n个整数，第i个数表示从左到右第i堆石堆的高度Ai。

1≤n≤50000,1≤Ai≤32768
Output

一个整数，“八阵锁”的数目。
Sample input and output

Sample Input     
5
1 2 3 4 1

Sample Output

6

题意：

让你寻找多少对满足i<j<k,a[i]<a[j],a[j]>a[k]

题解

我们对于每一个数，直接去寻找看在这个数前面，有多少个数比这个数小，在这个数后面，有多少个数比这个数下，然后乘起来相加就好啦

利用树状数组或者线段树啥，归并都能做到logn的时间搞定

~\(≧▽≦)/~啦啦啦

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 100001

#define mod 10007

#define eps 1e-9

const int inf=0x7fffffff;   //无限大

/*

inline ll read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

*/

//**************************************************************************************

int d[maxn];

int c[maxn];

int n;

int t;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int lowbit(int x)

{

    return x&-x;

}

void update(int x,int y)

{

    while(x<=t)

    {

        d[x]+=y;

        x+=lowbit(x);

    }

}

int sum(int x)

{

    int s=;

    while(x>)

    {

        s+=d[x];

        x-=lowbit(x);

    }

    return s;

}

int num[maxn];

int main()

{

    n=read();

    for(int i=;i<n;i++)

    {

        num[i]=read();

        t=max(t,num[i]);

    }

    ll ans1[maxn],ans2[maxn];

    ll ans=;

    for(int i=;i<n;i++)

    {

        ans1[i]=sum(num[i]-);

        update(num[i],);

    }

    memset(d,,sizeof(d));

    for(int j=n-;j>=;j--)

    {

        ans2[j]=sum(num[j]-);

        update(num[j],);

    }

    for(int i=;i<n;i++)

    {

        ans+=ans1[i]*ans2[i];

        //cout<<ans1[i]<<" "<<ans2[i]<<endl;

    }

    cout<<ans<<endl;

}