HDU 5273

3

//由于N只有1000,所以先打表。。。感觉自己好笨 打表想了好久 。。唉

#include <stdio.h>
#include <algorithm>
using namespace std;
int c[1010][1010]={{0}};
int arr[1010]={9999999};
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    int a,b;
    for(int i=999;i>=0;i--)  //计算每个i-k 有多少组
    {
        int cnt=0;
        for(int k=i+1;k<=1000;k++)
        {
            if(arr[i]>arr[k])
                cnt++;    
            c[i][k]=c[i+1][k]+cnt; //c[i][k]=c[i+1][k]+cnt[k]   
        }
    }
    while(m--)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",c[a][b]);
    }
    return 0;
}

HDU 5273

原文：http://blog.csdn.net/a73265/article/details/46575649