[HDU 6318] Swaps and Inversions

[题目链接]

http://acm.hdu.edu.cn/showproblem.php?pid=6318

[算法]

线段树 / 树状数组

[代码]

#include<bits/stdc++.h>

using namespace std;

#define MAXN 100010

long long i,n,x,y,len,ans,l,r,mid;

long long a[MAXN],rk[MAXN],tmp[MAXN];

struct SegmentTree

{

        struct Node

        {

                long long l,r;

                long long sum;

        } Tree[MAXN << ];

        inline void build(long long index,long long l,long long r)

        {

                long long mid;

                Tree[index].l = l;

                Tree[index].r = r;

                Tree[index].sum = ;

                if (l == r) return;

                mid = (l + r) >> ;

                build(index << ,l,mid);

                build(index <<  | ,mid + ,r);

        }

        inline void add(long long index,long long pos,long long val)

        {

                long long mid;

                Tree[index].sum += val;

                if (Tree[index].l == Tree[index].r) return;

                mid = (Tree[index].l + Tree[index].r) >> ;

                if (mid >= pos) add(index << ,pos,val);

                else add(index <<  | ,pos,val);

        }

        inline long long query(long long index,long long l,long long r)

        {

                long long mid;

                if (l > r) return ;

                if (Tree[index].l == l && Tree[index].r == r) return Tree[index].sum;

                mid = (Tree[index].l + Tree[index].r) >> ;

                if (mid >= r) return query(index << ,l,r);

                else if (mid +  <= l) return query(index <<  | ,l,r);

                else return query(index << ,l,mid) + query(index <<  | ,mid + ,r);

        }

} T;

int main()

{

        while (scanf("%lld%lld%lld",&n,&x,&y) != EOF)

        {

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

                {

                        scanf("%lld",&a[i]);

                        tmp[i] = a[i];

                }

                sort(tmp + ,tmp + n + ,greater<int>());

                len = ;

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

                {

                        if (tmp[i] != tmp[i - ])

                                tmp[++len] = tmp[i];

                }

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

                {

                        l = ; r = len;

                        while (l <= r)

                        {

                                mid = (l + r) >> ;

                                if (a[i] >= tmp[mid]) r = mid - ;

                                else l = mid + ;

                        }

                        rk[i] = l;

                }

                T.build(,,len);

                ans = ;

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

                {

                        ans += T.query(,,rk[i] - );

                        T.add(,rk[i],);

                }

                printf("%lld\n",1ll * ans * min(x,y));

        }

        return ;

}