逆序对线段树写法求助，悬赏关注两个

题目：

描述

给定序列

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

时的答案。

样例

输入

CPP

6
5 4 2 6 3 1

输出

CPP

0 1 3 4 7 11

我的代码

CPP

#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);
    }
}

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

CPP

0 1 3 3 6 11

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

逆序对线段树写法求助，悬赏关注两个

讨论操作

描述

输入

输出

样例

回复

相关推荐

逆序对线段树写法求助，悬赏关注两个