Problem Description
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
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
3 2
3 2 1
1 2
1 3
Sample Output
1
3
直接樹狀數組預處理出所有情況,然後輸出即可
#include<iostream>
#include<cstdio>
#include<vector>
#include<iostream>
#include<queue>
#include<cstdlib>
#include<map>
using namespace std;
const int maxn = 1005;
const int low(int x){ return x&-x; }
int f[maxn];
int a[maxn], b[maxn], c[maxn][maxn];
map<int, int> M;
int n, q, tot, l, r;
void add(int x)
{
for (int i = x; i <= tot; i += low(i)) f[i]++;
}
int sum(int x)
{
int ans = 0;
for (int i = x; i; i -= low(i)) ans += f[i];
return ans;
}
int main()
{
while (scanf("%d%d", &n, &q) != EOF)
{
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i - 1] = a[i];
sort(b, b + n);
for (int i = tot = 0; i < n; i++) M[b[i]] = ++tot;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= tot; j++) f[j] = 0;
c[i][i] = 0; add(M[a[i]]);
for (int j = i + 1; j <= n; j++)
{
c[i][j] = c[i][j - 1] + j - i - sum(M[a[j]]);
add(M[a[j]]);
}
}
while (q--)
{
scanf("%d%d", &l, &r);
printf("%d\n", c[l][r]);
}
}
return 0;
}