题意
给一个0 ~ n - 1
的排列,$k = \lbrace 0, 1, 2 … n - 1 \rbrace $,将数组向前移动k位,即看成一个链。
分别输出每一次的逆序对数。
思路
先求出第一次k = 0的逆序对数。
这里我用树状数组求的,不能有0, 所以将所有数全部加了1,如果不加后面公式需要更改。
然后考虑将前面第一个数放到最后所产生的变化。
对答案的影响是:加上比这个数大的,减去比这个数小的。
因为是一个排列,所以比当前数大的有$n - i$个,比当前数小的有$i - 1$个。
所以 ans += n - i * 2 + 1
。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 300010;
int n;
int tr[N], a[N];
void add(int a, int b)
{
for(int i = a; i <= n; i += i & -i)
tr[i] += b;
}
int query(int x)
{
int ans = 0;
for(int i = x; i > 0; i -= i & -i)
ans += tr[i];
return ans;
}
void solve()
{
cin >> n;
LL ans = 0;
for(int i = 0; i < n; i ++)
{
cin >> a[i];
a[i] ++;
add(a[i], 1);
ans += query(n) - query(a[i]);
}
for(int i = 0; i < n; i ++)
{
cout << ans << endl;
ans += n - a[i] * 2 + 1;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
/*int t;
cin >> t;
while(t --)*/
solve();
}
扩展
如果不是排列,是随机的一些数的话
把答案行计算大于和小于当前数的个数,用树状数组算即可
ans += query(n) - query(a[i]) - query(a[i] - 1)