hdu2838树状数组解逆序

离散化和排序后的序号问题搞得我实在是头痛

不过树状数组解逆序和偏序一类问题真的好用

更新：hdu的数据弱的真实，我交上去错的代价也对了。。

下面的代码是错的

/*

每个点的贡献度=权值*在这个点之前的比它大的点数量+在这个点前面比它大的所有点之和

开两个树状数组，一个保存相应序号的点值，另一个保存相应序号的

*/

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define maxn 100005

struct node{

    int x,id;

    bool operator<(const node & a)const{

        return x<a.x;

    }

}a[maxn];

int b[maxn];//b数组按输入顺序维护每个点的权值，序号

ll bit1[maxn],bit2[maxn];

int n;

void add1(int x){

    for(int i=x;i<=maxn;i+=i&-i)

        bit1[i]++;

}

void add2(int x,int num){

    for(int i=x;i<=maxn;i+=i&-i)

        bit2[i]+=num;

}

ll query1(int x){

    ll res=;

    for(int i=x;i;i-=i&-i)

        res+=bit1[i];

    return res;

}

ll query2(int x){

    ll res=;

    for(int i=x;i;i-=i&-i)

        res+=bit2[i];

    return res;

}

int main(){

    while(scanf("%d",&n)==){

        for(int i=;i<=n;i++)

            scanf("%d",&a[i].x),a[i].id=i;

        sort(a+,a++n);

        for(int i=;i<=n;i++) b[a[i].id]=i;//其实就是一次映射,由于a数组进行了排序，该映射要找到原序列的每个数在排序后，在新的数组里的位置

        ll ans=;

        for(int i=;i<=n;i++){

            ans+=a[b[i]].x*(query1()-query1(a[b[i]].x));//通过映射i->b[i],找到每个数新的位置

            ans+=query2()-query2(a[b[i]].x);

            add1(b[i]);

            add2(b[i],a[b[i]].x);

        }

        printf("%lld\n",ans);

    }

    return ;

}

下面的代码是对的

#include<iostream>

using namespace std;

#define N 100001

int n;

struct node

{

    int index;

    __int64 sum;

}c[N];

int lowbit(int x)

{

    return x&(-x);

}

void update(int x,int k,int s)

{

    while(x<=n)

    {

        c[x].index+=k;

        c[x].sum+=s;

        x+=lowbit(x);

    }

}

int getsum_index(int x)

{

    int ans=;

    while(x>)

    {

        ans+=c[x].index;

        x-=lowbit(x);

    }

    return ans;

}

__int64 getsum_sum(int x)

{

    __int64 ans=;

    while(x>)

    {

        ans+=c[x].sum;

        x-=lowbit(x);

    }

    return ans;

}

int main(void)

{

    while(~scanf("%d",&n))

    {

        int i;

        __int64 ans=;

        memset(c,,sizeof(c));

        for(i=;i<=n;i++)

        {

            int x;

            scanf("%d",&x);

            update(x,,x);

            __int64 k1=i-getsum_index(x);

            if(k1!=)

            {

                __int64 k2=getsum_sum(n)-getsum_sum(x);

                ans=ans+k1*x+k2;

            }

        }

        printf("%I64d/n",ans);

    }

}