hdu 5273 Dylans loves sequence

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #define maxn 1010
 5 int dp[maxn][maxn],a[maxn];
 6 int main ()
 7 {
 8     int n, q;
 9     while (scanf ("%d %d", &n, &q) != EOF)
10     {
11         for (int i=1; i<=n; i++)
12             scanf ("%d", &a[i]);
13         memset (dp, 0, sizeof(dp));
14         for (int i=1; i<=n; i++)
15         {//dp[i][j]是[i,j]区间里i为起始位置的倒置数对
16             for (int j=i+1; j<=n; j++)
17                 if (a[i] > a[j])
18                     dp[i][j] ++;
19             for (int j=i+1; j<=n; j++)
20                 dp[i][j] += dp[i][j-1];
21         }
22         for (int i=n-1; i>0; i--)//再枚举[i,j]这个区间里面任意一个数为起始位置，含有的倒置数对
23             for (int j=i+1; j<=n; j++)
24                 dp[i][j] += dp[i+1][j];
25         while (q--)
26         {//最后输出结果
27             int l, r;
28             scanf ("%d %d", &l, &r);
29             printf ("%d\n", dp[l][r]);
30         }
31     }
32     return 0;
33 }