HDU 5273 Dylans loves sequence 暴力递推Dylans loves sequence

题目链接：

hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5273

bc:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=604&pid=1002

Dylans loves sequence

 

 Accepts: 250

 

 Submissions: 806

 Time Limit: 2000/1000 MS (Java/Others)

 

 Memory Limit: 131072/131072 K (Java/Others)

问题描述

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

Hint

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

题解：

　　如果已知[l,r]的逆序对要求[l,r+1]的逆序对，只需加上第r+1位对区间[l,r+1]贡献就可以了，而这个贡献值可以离线暴力求出来，那么久可以用o(n^2)暴力求出所有去加的逆序对数了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=1000+10;

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,0,sizeof(cnt));
    memset(dp,0,sizeof(dp));
}

int main(){
    while(scanf("%d%d",&n,&q)==2){
        init();
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
        }
        for(int i=2;i<=n;i++){
            for(int j=i-1;j>=1;j--){
                if(a[j]>a[i]) dp[i][j]=dp[i][j+1]+1;
                else dp[i][j]=dp[i][j+1];
            }
        }
        
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                cnt[i][j]=cnt[i][j-1]+dp[j][i];
            }
        }
        
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%dn",cnt[l][r]);
        }
    }
    return 0;
}