Dylans得到了N个数a[1]...a[N]。
有Q个问题，每个问题形如(L,R)
他需要求出L?R这些数中的逆序对个数。
更加正式地，他需要求出二元组(x,y)的个数，使得L≤x,y≤R且x<y且a[x]>a[y]

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#define N 1010

using namespace std;

int n,q;
int a[N],sum[N][N],num[N][N];

int main() {
    //freopen("test.in","r",stdin);
    while(~scanf("%d%d",&n,&q)) {
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        memset(num,0,sizeof num);
        //枚举开头  num[i][j]:以i开头，以j结尾的区间逆序对个数
        for(int i=1; i<=n; i++) {
            for(int j=i+1; j<=n; j++) {
                if(a[j]<a[i]) {
                    num[i][j]=num[i][j-1]+1;
                } else {
                    num[i][j]=num[i][j-1];
                }
            }
        }
        memset(sum,0,sizeof sum);
        ///预处理：sum[j][i]:以i结尾，以j开头的区间内所有逆序对数
        for(int i=1; i<=n; i++) {
            for(int j=i-1; j>=1; j--) {
                sum[j][i]=sum[j+1][i]+num[j][i];
            }
        }
        int l,r;
        while(q--) {
            scanf("%d%d",&l,&r);
            if(l==r) {
                printf("0\n");
                continue;
            }
            printf("%d\n",sum[l][r]);
        }
    }
    return 0;
}