飞机票：http://acm.hdu.edu.cn/showproblem.php?pid=5273

题意：给你N个数ai 1<=i<=n,N<=1000，以及Q个查询,Q<=100000，每个查询有两个整数L,R 求[L,R]逆序对的数量(逆序对就是当i<j 时，ai>aj)

分析：要求[L,R]之间的逆序对数量，且Q<=100000,我们可以O（n^2)的时间求出[i,j]之间的逆序对的数量，i<=j,然后用O（1）的时间查询答案，具体怎么算，我们先来个辅助数组fi[maxn][maxn]，其中maxn是题目给的最大N，因为N最大是1000，所以数组大小为1000000，不会爆空间，然后我们令fi[i][j]，表示以i为逆序对的端点，然后计算j从i~1，以j为右端点的总数，用递推就可以在O（n^2)算出来,接着来个sum[maxn][maxn]数组，这个数组就是答案，其中sum[i][j]表示从i到j一共用多少组逆序对，因为我们有fi数组，所以只要累加fi数组就可以了，j从i到n，然后sum[i][j]=sum[i][j-1]+fi[j][i];这个怎么解释，好好想想就知道了，假设我们要知道从i到j的sum，因为我们已经知道sum[i][j-1]的sum了，而以j结尾，且已i开始的之间的总数就是fi[j][i]，所以加上就是答案，复杂度O（n*n+Q),然后啪啪啪，就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234;
LL ai[maxn];
LL fi[maxn][maxn];
LL sum[maxn][maxn];
int n,Q;
void init()
{
    for(int i=1; i<=n; i++)scanf("%I64d",&ai[i]);
}
void play()
{

    memset(fi,0,sizeof(fi));
    memset(sum,0,sizeof(sum));
    for(int i=1; i<=n; i++)
    {
        fi[i][i]=0;
        for(int j=i-1; j>=1; j--)
        {
            fi[i][j]=fi[i][j+1];
            if(ai[i]<ai[j])
            {
                fi[i][j]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        sum[i][i]=0;
        for(int j=i+1;j<=n;j++){
            sum[i][j]=sum[i][j-1]+fi[j][i];
        }
    }
    int L,R;
    while(Q--)
    {
        scanf("%d%d",&L,&R);
        printf("%I64d\n",sum[L][R]);
    }

}
int main()
{
    while(scanf("%d%d",&n,&Q)!=EOF)
    {
        init();
        play();
    }
    //    cout << "Hello world!" << endl;
    return 0;
}