HOJ 2275——Number sequence(樹状配列)

Number sequence
My Tags
  (Edit)
 
ソurce : SCU Prograamming Contact 2006 Final
 
Time limit : 1 sec
 
メモリ : 64 m
Submitted : 1540、 Acceepted : 417
Gven a number sequence which has N element(s)、please callate the number of different collection for three number Ai、Aj、Ak、which satisfy that Ai＜Aj＞Ak and i＜j＞Ak.i
Input
The first line is an integer N(N<=50000).The second line contains N integer(s):A 1,A 2,…,An(0==Ai<=32768).
Output
The e e e is only one number,which is the number of different collection.
Sample Input

5
1 2 3 4 1

Sample Output

6

————————————————線を分割——————————————————————————————————————
タイトルの大意:
n個の数を与えて、Ai＜Aj＞Ak and i＜j＜k.の合計を満たす組み合わせの数を求めます.
考え方:
i番目の数については、そのより小さい数の個数aを順次統計し、それより小さい個数bを逆順で統計すると、左右の両方の小さな数の個数が得られます.i番目の数のスキーム数はa*bです.
また、この問題はEOFが終わったとは言いませんでしたが、EOFがなかったら間違いです.何発も間違えました.

#include
#include
#include
#define Local
#define M 50000+10
#define maxn 32768
#define ll long long
using namespace std;
int a[M],b[M],c[M];
void modify(int x,int v)
{
    for(int i=x;i<=M;i+=i&-i){
        c[i]+=v;
    }
}
int getsum(int x)
{
    int sum=0;
    for(int i=x;i>0;i-=i&-i){
        sum+=c[i];
    }
    return sum;
}
int main()
{
#ifdef local
    freopen("in.txt","r",stdin);
    freopen("ou.txt","w",stdout);
#endif // local

    int n;
    while(scanf("%d",&n)!=EOF){
        memset(c,0,sizeof(c));
        ll sum=0;
        for(int i=0;i=0;--i){
            sum+=(ll)getsum(a[i]-1)*b[i];
            modify(a[i],1);
        }
        printf("%lld
",sum);
    }
    return 0;
}