Dylans loves sequence
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 195Accepted Submission(s): 105
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 numbersN 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]≤2311
Output
For each query,print the numbers of "inversions”
Sample Input
3 23 2 11 21 3
Sample Output
13
Hint
You shouldn’t print any space in each end of the line in the hack data.
Source
BestCoder Round #45
题目大意：求区间逆序数对数题目分析：用dp[i][j]预处理，，先算区间[i,j]中与a[i]成逆序对的数目，然后从后向前累加，相当于加一个a[j]，看它对整个区间的逆序数对数是否有影响#include <cstdio>#include <cstring>int const MAX = 1005;int dp[MAX][MAX];int a[MAX];int main(){int n, q;scanf("%d %d", &n, &q);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; i++)for(int j = i; j <= n; j++)dp[i][j] += (dp[i][j – 1] + (a[i] > a[j] ? 1 : 0));for(int j = n; j > 0; j–)for(int i = j; i > 0; i–)dp[i][j] += dp[i + 1][j];while(q–){int l, r;scanf("%d %d", &l, &r);printf("%d\n", dp[l][r]);}}
最大的成功在于最大的付出。
