Dylans loves sequence

Dylans得到了NN个数a[1]...a[N]a[1]...a[N]。

有QQ个问题，每个问题形如(L,R)(L,R)

他需要求出L-RL−R这些数中的逆序对个数。

更加正式地，他需要求出二元组(x,y)(x,y)的个数，使得L \leq x,y \leq RL≤x,y≤R且x < yx<y且a[x] > a[y]a[x]>a[y]

第一行有两个数NN和QQ。

第二行给出NN个数字a[1]...a[N]a[1]...a[N]。

接下来的QQ行，每行给出两个数L, RL,R。

N \leq 1000,Q \leq 100000,L \leq R,1 \leq a[i] \leq 2^{31}-1N≤1000,Q≤100000,L≤R,1≤a[i]≤2​31​​−1

对于每个询问，输出逆序对个数。

3 2

3 2 1

1 2

1 3

1

3

hack数据里读入的每一行末尾不应该有多余的空格。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=+;

int n,q;

int a[maxn];

//cnt[i][j]表示区间[i,j]的逆序对数

int cnt[maxn][maxn];

//dp[i][j]表示第i位对区间[j,i](j<i)的逆序对贡献值

int dp[maxn][maxn];

void init(){

    memset(cnt,,sizeof(cnt));

    memset(dp,,sizeof(dp));

}

int main(){

    while(scanf("%d%d",&n,&q)==){

        init();

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

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

        }

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

            for(int j=i-;j>=;j--){

                if(a[j]>a[i]) dp[i][j]=dp[i][j+]+;

                else dp[i][j]=dp[i][j+];

            }

        }

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

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

                cnt[i][j]=cnt[i][j-]+dp[j][i];

            }

        }

        while(q--){

            int l,r;

            scanf("%d%d",&l,&r);

            printf("%d\n",cnt[l][r]);

        }

    }

    return ;

}