【Foreign】朗格拉日计数 [暴力]

朗格拉日计算

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

　　

Input

　　

Output

　　仅一行一个整数表示答案。

Sample Input

　　5
　　3 2 5 4 1

Sample Output

　　4

HINT

　　

Main idea

　　将一个排列围成一个环，每个点有一个值a[i]，若顺时针三个点A、B、C 满足 a[A]<a[B]<a[C] 则可以统计答案，询问答案。

Solution

　　我们不考虑环，从序列考虑，显然可以统计的就是类似这种：123、231、312这个样子的。

　　我们考虑容斥，显然123这种是可以直接计算的，231就是xx1 - 321，312就是3xx - 321。

　　显然我们这样这样用树状数组统计一下 f[i] 表示 i 前面<a[i]的个数，然后就可以计算出：前面<a[i]的个数、前面>a[i]的个数、后面<a[i]的个数、后面>a[i]的个数。

　　然后这样暴力计算即可。

Code

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int MOD = 1e9+;

 int n;

 int a[ONE],f[ONE];

 s64 Ans;

 int get()

 {

         int res=,Q=;    char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 s64 C(int n)

 {

         return (s64)n*(n-)/;

 }

 namespace Bit

 {

         int C[ONE];

         int lowbit(int x)

         {

             return x&-x;

         }

         void Add(int R,int x)

         {

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

                 C[i]+=x;

         }

         int Query(int R)

         {

             int res=;

             for(int i=R;i>=;i-=lowbit(i))

                 res+=C[i];

             return res;

         }

 }

 int pre_min(int i) {return f[i];}

 int pre_max(int i) {return i--f[i];}

 int suc_min(int i) {return a[i]--pre_min(i);}

 int suc_max(int i) {return n-a[i]-pre_max(i);}

 int main()

 {

         n=get();

         for(int i=;i<=n;i++)    a[i]=get();

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

         {

             Bit::Add(a[i],);

             f[i] = Bit::Query(a[i]-);

         }

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

         {

             Ans += (s64)pre_min(i) * suc_max(i);

             Ans += C( pre_max(i) );

             Ans += C( suc_min(i) );

             Ans -= (s64) * pre_max(i) * suc_min(i);

         }

         printf("%lld",Ans);

 }