hdu 5273 Dylans loves sequence Dylans loves sequence

92 阅读 0 评论 61 点赞

我是靠谱客的博主腼腆保温杯，最近开发中收集的这篇文章主要介绍hdu 5273 Dylans loves sequence Dylans loves sequence，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Dylans loves sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 117 Accepted Submission(s): 61

Problem Description

Dylans is given

N numbers

a[1]....a[N]

And there are

Q questions.

Each question is like this

(L,R)

his goal is to find the “inversions” from number

L to number

R .

more formally,his needs to find the numbers of pair（

x,y ）,
that

L≤x,y≤R and

x<y and

a[x]>a[y]

Input

In the first line there is two numbers

N and

Q .

Then in the second line there are

N numbers:

a[1]..a[N]

In the next

Q lines,there are two numbers

L,R in each line.

N≤1000,Q≤100000,L≤R,1≤a[i]≤231−1

Output

For each query,print the numbers of "inversions”

Sample Input

Sample Output

  
  
   
   1
3


   
   
    
    
     
     Hint
    
    
You shouldn't print any space in each end of the line in the hack data.

Source

BestCoder Round #45

Recommend

hujie | We have carefully selected several similar problems for you: 5275 5274 5271 5270 5269

题意

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("0n");
                continue;
            }
            printf("%dn",sum[l][r]);
        }
    }
    return 0;
}