[ An Ac a Day ^_^ ] hdu 3743 Frosh Week 离散化+树状数组

昨天的BC又复习了一遍离散化 加上下学期还要讲树状数组 就把树状数组求逆序数再拿出来做做

也写了好久 遇到了几个小坑

首先 for要从1~n 而不是0~n-1

因为树状数组里0代表的是结束 而不是一个数值

然后 需要离散化适用的情况是数据范围大 而数据少的时候

最后 很多个int加到一起可能是ll 记得看范围

#include<bits/stdc++.h>
#define cl(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr<<#x<<"=="<<(x)<<endl
using namespace std;
typedef long long ll;

const int maxn=5e5+10;

int tree[maxn],n;

struct number
{
    int id,num;
}num[maxn];

bool cmp(number a,number b)
{
    return a.num>b.num;
}

int lowbit(int x)
{
    return x&(-x);
}

void add(int x)
{
    int sum=0;
    while(x<=n)
    {
        tree[x]++;
        x+=lowbit(x);
    }
}

int getsum(int x)
{
    int sum=0;
    while(x>=1)
    {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num[i].num);
            num[i].id=i;
        }
        sort(num+1,num+n+1,cmp);//排序
        cl(tree,0);//初始化
        ll sum=0;
        add(num[1].id);
        for(int i=2;i<=n;i++)//从大到小向树状数组中加入
        {
            sum+=getsum(num[i].id);//计算当前位数右边比它大的数的sum
            add(num[i].id);//将当前数加入树状数组
        }
        printf("%lld
",sum);
    }
    return 0;
}
/*

3
3 1 2

*/