题意：求任意一个区间的逆序对
思路：f[i][j]表示i到j之间与点j的逆序对，dp[i][j]表示i到j这区间的逆序对，dp[i][j]=dp[i][j-1]+f[i][j]
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1002; 4 5 int a[N]; 6 int f[N][N]; 7 int dp[N][N]; 8 9 int main(){ 10 int n,q; 11 scanf("%d%d",&n,&q); 12 for(int i=1;i<=n;i++) 13 scanf("%d",&a[i]); 14 for(int i=1;i<=n;i++){ 15 f[i][i]=0; 16 for(int j=i-1;j>=1;j--){ 17 if(a[i]<a[j]){ 18 f[j][i]=f[j+1][i]+1; 19 } 20 else f[j][i]=f[j+1][i]; 21 } 22 } 23 for(int i=2;i<=n;i++){ 24 for(int l=1;i<=n;l++){ 25 if(l+i-1>n) break; 26 int r=l+i-1; 27 dp[l][r]=dp[l][r-1]+f[l][r]; 28 // cout<<l<<" "<<r<<" "<<f[l][r]<<endl; 29 } 30 } 31 while(q--){ 32 int x,y; 33 scanf("%d%d",&x,&y); 34 cout<<f[x][y]<<endl; 35 } 36 return 0; 37 }