这道题的n限制在500以内,那当然可以使得暴力,优雅得度过这道题。
但是我们都知道,算法是要挑战极限的。如果n变得很大,该如何做这道题呢?
我们发现要产生这么一个符合条件的四元组,最重要的要寻得 符合条件的b,c,那么a就在c之前比b小,d就在c之后比b大。
因此这道题用主席树能够很好的优美的度过这道题。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=505; int root[N],a[N]; struct node{ int l,r,sum; }e[N*40]; int cnt; void build(int x,int &y,int l,int r,int k){ if(l>r)return; y=++cnt; e[y]=e[x]; e[y].sum++; if(l==r)return; int mid=l+r>>1; if(k<=mid)build(e[x].l,e[y].l,l,mid,k); else build(e[x].r,e[y].r,mid+1,r,k); } ll query(int dex,int L,int R,int l,int r){ if(L>R)return 0; if(l>=L&&r<=R)return e[dex].sum; if(l>R||r<L)return 0; int mid=l+r>>1; return query(e[dex].l,L,R,l,mid)+query(e[dex].r,L,R,mid+1,r); } int main(){ int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)build(root[i-1],root[i],1,n,a[i]); ll ean=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(a[i]>a[j]){ ll x=query(root[i-1],1,a[j]-1,1,n); ll y=query(root[n],a[i]+1,n,1,n)-query(root[j-1],a[i]+1,n,1,n); ean+=x*y; } } } cout<<ean<<endl; }