题目：

描述

给定序列 $a1,a2,…,an$，求所有后缀的逆序对个数。即对每个 $i$，求有多少对 $(j,k)$满足 $i≤j<k≤n$且 $aj>ak$。

输入

第一行是正整数$n$。保证 $1≤n≤5×105$。

第二行 $n$ 个互不相同的正整数，表示 $a$ 。保证 $1≤ai≤n$ 。

输出

空格隔开的$n$ 个整数，表示 $i=n,n−1,…,1$ 时的答案。

样例

输入

6
5 4 2 6 3 1

输出

0 1 3 4 7 11

我的代码

#include<iostream>
using namespace std;

typedef long long ll;

const int maxn=1e6;

struct node{
    ll sum;
    ll tag;
}tree[maxn<<2];

ll arr[maxn+5];

void pushUp(ll root){
    tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
}

void pushDown(ll root,ll ln,ll rn){
    if(tree[root].tag){//Has tag
        tree[root<<1].sum+=ln*tree[root].tag;
        tree[root<<1|1].sum+=rn*tree[root].tag;
        tree[root].tag=0;
    }
    return ;
}

void build(ll l,ll r,ll root){
    if(l==r){
        tree[root].sum=arr[l];
        return ;
    }
    ll mid=(l+r)>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    pushUp(root);
    return ;
}

void updateQ(ll l,ll r,ll L,ll R,ll v,ll root){//区间更新
    if(L<=l && r<=R){
        tree[root].sum+=(r-l+1)*v;
        return ;
    }
    ll mid=(l+r)>>1;
    ll ln=mid-l+1,rn=r-mid;
    pushDown(root,ln,rn);
    if(L<=mid){
        updateQ(l,mid,L,R,v,root<<1);
    }
    if(R>mid){
        updateQ(mid+1,r,L,R,v,root<<1|1);
    }
    pushUp(root);//update
    return ;
}

ll query(int l,int r,int L,int R,int root){
    ll sum=0;
    if(L<=l && r<=R){
        return tree[root].sum;
    }
    ll mid=(l+r)>>1;
    ll ln=mid-l+1;
    ll rn=r-mid;
    if(L<=mid){
        sum+=query(l,mid,L,R,root<<1);
    }
    if(mid<R){
        sum+=query(mid+1,r,L,R,root<<1|1);
    }
    return sum;
}

int main(){
    ll n,m;
    cin>>n;
    int t=0,l,r,v;
    int ans=0;
    for(int i=1;i<=n;i++){
        cin>>t;
        ans+=query(1,n,t+1,n,1);
        updateQ(1,n,t,t,1,1);
        printf("%d ",ans);
    }
}

我的代码在当前样例下的输出是

0 1 3 3 6 11

仅能保证最终的逆序对个数正确，不知道为什么