珂朵莉的数列
求所有子区间的逆序数之和,我们观察每一对逆序(ai, aj),发现这个逆序被计算了i*(n+1-j)次,即区间起点在i之前,终点在j之后,那么我们在用归并排序求逆序和的时候,把权值换成第一区间内剩余元素的下标之和就行了。
#include <cstdio>
using namespace std;
typedef long long ll;
typedef __int128 bigint;
const int maxn = 1e6+5;
struct node{
ll val, idx;
}node[maxn], tmp[maxn];
int n;
bigint ans;
inline void Swap(){
return;
}
ll msort(int l, int r){
if (l==r) return node[l].idx;
int mid = (l+r)/2;
ll left = msort(l, mid), right = msort(mid+1, r);
ll res = left + right;
int i=l, j=mid+1, cur=l;
while (i<=mid && j<=r){
if (node[i].val <= node[j].val) tmp[cur++] = node[i] , left -= node[i].idx, i++;
else{
ans += left*(n+1-node[j].idx);
right -= node[j].idx;
tmp[cur++] = node[j];
j++;
}
}
while (i<=mid) tmp[cur++] = node[i++];
while (j<=r) tmp[cur++] = node[j++];
for (int x=l; x<=r; x++) node[x] = tmp[x];
return res;
}
void output(bigint x){
if (x<10){
int t = x;
printf ("%d", t);
return;
}
output(x/10);
int t = x%10;
printf ("%d", t);
return;
}
int main(){
scanf ("%d", &n);
for (int i=1; i<=n; i++){
scanf ("%lld", &node[i].val);
node[i].idx = i;
}
ans = 0;
msort(1, n);
output(ans);
return 0;
}
0 条评论