首页技术正文

HDU 5273 Dylans loves sequence 暴力递推

程序员高坡技术 2022年11月11日

0 收藏 636 点赞 4,381 浏览 1337 个字

题目链接：

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]≤231−1

输出描述

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

输入样例

输出样例

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=+;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 ;
}