珂朵莉的数列

求所有子区间的逆序数之和,我们观察每一对逆序(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 条评论

发表评论

邮箱地址不会被公开。