Dylans loves sequence(hdu5273)

Dylans loves sequence

Time Limit: 2/1 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 385    Accepted Submission(s): 193


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 Lx,yR 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.

N1,Q100,LR,1a[i]2311
 

 

Output
For each query,print the numbers of "inversions”
 

 

Sample Input
3 2 3 2 1 1 2 1 3
 

 

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
 

 

 

 

 1 #include <stdio.h>
 2 #include <string.h>
 3 int ans[1010][1010],s[1010],cnt[1010];
 4 int main()
 5 {
 6     int n,m,i,j,sum,l,r;
 7     scanf("%d %d",&n,&m);
 8     for(i=1;i<=n;i++)
 9     {
10         scanf("%d",&s[i]);
11     }
12     for(i=1;i<=n;i++)
13     {
14         sum=0;
15         for(j=1;j<=i;j++)
16         {
17             if(s[i]<s[j])
18             {
19                 sum++;
20             }
21         }
22         ans[1][i]=ans[1][i-1]+sum;
23     }
24     for(i=2;i<=n;i++)
25     {
26         memset(cnt,0,sizeof(cnt));
27         for(j=i;j<=n;j++)
28         {
29             if(s[i-1]>s[j])
30             {
31                 cnt[j]=cnt[j-1]-1;
32             }
33             else
34             {
35                 cnt[j]=cnt[j-1];
36             }
37             ans[i][j]=ans[i-1][j]+cnt[j];
38         }
39     }
40     while(m--)
41     {
42         scanf("%d %d",&l,&r);
43         printf("%d\n",ans[l][r]);
44     }
45     return 0;
46 }

 

更多相关文章
  • hdu 5273 Dylans loves sequence
    题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=5273 Dylans loves sequence Description Dylans is given $N$ numbers $a[1]....a[N]$ And there are $Q$ que
  • hdu 5272 Dylans loves numbers
    题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=5272 Dylans loves numbers Description Who is Dylans?You can find his ID in UOJ and Codeforces.His anoth
  • hdu Dylans loves tree
    Dylans loves tree   view code#pragma comment(linker, "/STACK:1024,1024") #include <iostream> #include <algorithm> #include <c ...
  • HDU 5273 Dylans loves numbers(水題)
      题意:给出一个0≤N≤1018,求其二进制中有几处是具有1的,假设相连的1只算1处,比如1101011就是3处. 思路:一个个数,当遇到第一个1时就将flag置为1:当遇到0就将flag置为0.当遇到1时,flag=0就统计,当flag=1时就不统计.   1 #include <bits ...
  • Dylans loves sequence Time Limit: 2/1 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total S
  • 第五周 6.146.20
    6.14-6.15 什么都没干.   6.16 好久没码题了.快结课了会空很多.但在时间上
  • bestcoder#45 1002 求区间的逆序数  树状数组
    bestcoder#45 1002 求区间的逆序数  树状数组 Dylans loves sequence    Accepts: 250    Submissions: 806  Time Limit: 2/1 MS (Java/Others)    Memory Limit: 131072/13 ...
  • (bc #45) A
    Dylans loves numbers Time Limit: 2/1 MS (Java
一周排行