thair

好，这个naive的东西因为只有三元，很好求解。只要把每个数之前小的L[i]与之后大的R[i]求一下即可。

求两次逆序对即可。那么答案便是∑(L[i]*R[i]);

对于更高元的，胡雨菲写的是要用DP

那么先放水的一批的代码

(就这还洛谷蓝题，我直接给的黄题)

 

1 #include 
      
        2 #include 
       
         3 #define lowbit(a) (a&(-a)) 4 using namespace std; 5 const int N = 30010; 6 int x[N],tree[N],n,a[N],L[N],R[N]; 7  8 void add(int x,int v) 9 {10     if(x==0) return;11     for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=v;12     return;13 }14 int getsum(int x)15 {16     if(x==0) return 0;17     int ans=0;18     for(int i=x;i>0;i-=lowbit(i)) ans+=tree[i];19     return ans;20 }21 22 23 24 int main()25 {26     scanf("%d",&n);27     for(int i=1;i<=n;i++) scanf("%d",&a[i]),x[i]=a[i];28     sort(x+1,x+n+1);29     int k=0;30     for(int i=1;i<=n;i++) if(x[i]!=x[i-1]) x[++k]=x[i];31 32     for(int i=1;i<=n;i++)33     {34         int p=lower_bound(x+1,x+k+1,a[i])-x;35         L[i]=getsum(p-1);36         add(p,1);37     }38     fill(tree+1,tree+n+1,0);39     for(int i=n;i>=1;i--)40     {41         int p=lower_bound(x+1,x+k+1,a[i])-x;42         R[i]=(n-i)-getsum(p);43         add(p,1);44     }45     long long ans=0;46     for(int i=1;i<=n;i++) ans+=L[i]*R[i];47     printf("%lld",ans);48     return 0;49 }