vijos p1768 数学

链接：点我

预处理：b[i][j]表示a[1] ... a[j]中比a[i]小的数的数量。
设
int get_lower_count(int b[], int l, int r)
{
return b[r] - b[l - 1];
}
枚举左端点i，右端点j，则 get_lower_count(b[j], i + 1, j) - get_lower_count(b[i], i,

j)为a[i]...a[j]的“顺序对的值”。因为a...a[j-1]中的值只有3种情况，要么比a[j]大，要么在a[i]与a[j]之间，要么比
a[i]小。比a[i]小的数，必然比a[j]小。所以用比a[j]小的数剪掉比a[i]小的数即可。

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 typedef long long ll;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt,a[MAXN],f[MAXN][MAXN];   //1到j中比a[i]小的数

 int main()

 {

     int i,j,k;

     /*#ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif*/

     scanf("%d",&n);

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

     {

         scanf("%d",a+i);

     }

     cl(f);

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

     {

         f[i][]=(a[i]>a[]);

         for(j=;j<=n;j++)

         {

             f[i][j]=f[i][j-]+(a[j]<a[i]);

         }

     }

     long long ans=,ans1,ans2;

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

     {

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

         {

             if(a[j]>a[i])

             {

                 ans1=f[j][j]-f[j][i];   //i到j内比a[j]小的数(注意这里不包含i和j)

                 ans2=f[i][j]-f[i][i];   //i到j内比a[i]小的数

                 ans+=(ans1-ans2);

                 //printf("%d %d %d %d %d\n",i,j,ans1,ans2,ans);

             }

         }

     }

     printf("%I64d\n",ans);

 }

巴特西

vijos p1768 数学

最新文章

热门文章