hdu--4911--归并排序||树状数组

发现一个小小的 逆序数里真的藏了好多东西啊=-=

解决这题 你需要知道一点...

对于一串给定的数字 我随便写一串吧..

index:   0　　1　　2　　3　　4

value:　4　　8　　7　　5　　6    这时候 总的逆序对数是  3+2=5   假如我们只能进行相邻元素的交换 这最好情况是什么呢？

那肯定就是假如本来 arr[x]>arr[x+1] 那这样是形成一个逆序数的吧 我们将它进行交换 这样就少了一个逆序数对是吧...

但是 对于其它位置的元素是没有影响的对吧

所以 我们需要的最小次数呢 就是sum<即原数组的逆序数个数> 然后把它和k比较下大小就是了

看到了disucss里面的帖子 才第一次 知道 sort是不稳定的排序...这题里要用stable_sort。。没用树状数组去写-呆会写

每天mhxy 和lol 玩来玩去  超累啊=-=

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
LL sum;
const int size = 100010;
int arr[size];
int temp[size];

void merge_sort( int l , int r )
{
    int mid , p , q , i;
    if( r-l > 1 )
    {
        mid = l + (r-l) / 2;
        p = l;
        q = mid;
        i = l;
        merge_sort( l , mid );
        merge_sort( mid , r );
        while( p<mid || q<r )
        {
            if( q>=r || (p<mid && arr[p] <= arr[q] ) )
            {
                temp[i++] = arr[p++];
            }
            else
            {
                temp[i++] = arr[q++];
                sum += (mid-p);
            }
        }
        for( i = l ; i<r ; i++ )
        {
            arr[i] = temp[i];
        }
    }
}

int main()
{
    cin.sync_with_stdio(false);
    int n;
    LL k;
    while( cin >> n >> k )
    {
        sum = 0;
        for( int i = 0 ; i<n ; i++ )
        {
            cin >> arr[i];
        }
        merge_sort( 0 , n );
        cout << max( sum-k , (LL)0 ) << endl;
    }
    return 0;
}

这边要注意下 0的前面要用LL进行强制转换 不然会CE..因为前者是LL类型的..

做逆序数对的时候 很容易会是用到64位的 因为 假如给你这么组BT数组  X , X-1 , X-2 , X-3 , …………x-i,x-i-1,…………,1  那就是Ah 等差数列求和#24.。

这边留一大片空白 给待会写的 树状数组....

突然 想再写点关于刚刚的归并排序的一些东西<因为我觉得归并很难啊 我最烦这种递归的了 卧槽..真羡慕那些写递归和写for一样的人..#80>

似乎 归并排序的 分治操作将它不断进行二分的操作 最终在分成只有一个元素的时候 结束了递归

然后开始一步步从结束递归的那个函数慢慢地回去向上操作.  可能 我们将  2 1 4 3 这4个元素 进行归并操作 那么我们是这样进行的吧

<2,1,4,3>---><2,1> , <4,3>       <2,1>----><2.>,<1.>       <4,3>----><4,>,<3>    

先是要比较 2 和 1的大小关系 1小于2 那么先复制右边空间的数组  这里的左右以 Mid 为分界线  同时 如果是要进行逆序数对数个数统计的操作 那么这时候就需要mid-p了来计算此时左空间总共的数据个数这边不用担心会重复计算 因为当你左右空间全部遍历结束以后 它就会进行合并操作了 一起算到上一个更大的左/右区间之一了

--------恩 好像就暂时自己能想到这些地方吧 可能有错误 不可尽信 ..

不得不吐槽下 在写下上述东西的时候 垃圾电信 网断了大概6 7次 我草了...

****************************************************下面是树状数组

这题呢 一定要用离散化了 因为数据数量大小是10^5   但是数据元素大小是10^9 显然是>>的关系 所以要进行离散化了

感觉这 3个字 真心很好听啊 高大上 orz。。

最通俗的解释就是原来我们用a[]数组存储输入数据是

index: 0　　1　　2　　3　　4

value: 666   888 777   999  555

那么离散后要是我们是将数据存到b数组中的话 那么结果就是

index:0　　1　　2　　3　　4

value:1　　3　　2　　4　　0 //这边数是从0开始  当然从1开始也可以

对于这题  因为你是要用到树状数组 那就一定要从1开始了 原因的话就是上次讲得 不然会进入到死循环之中的

这边的离散化细节 网上有篇介绍的真心不错 我把它拿过来

　　　　传送

如果你首先 看到这个链接 就可以X掉我这个页面了=-=

那么 我就随便扯点好了..

对于update() 和 getSum()函数体内写什么内容 都是由你的tree[x]数组的含义而定 你可以把它定义为>=x的元素有几个  或者是 <=x的元素有几个 这些都可以

然后再用getSum(x)就是求得当前插入的这么多元素中 >=x / <=x的元素有几个

这样的话 我们求得的getSum()中总是包含了自身

我可以将tree[x]定义为 大于x的元素有几个不包括等于

我只要这样写 update( arr[i]-1 , 1)   ans+=getSum(arr[i]) 这样就可以了

另外tree[x]小于x的写法 我这边不写了 自己去试下吧

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
int n;
const int size = 100010;
struct data
{
    int id;
    int val;
}node[size];
int tree[size];
int arr[size];

bool cmp( const data p , const data q )
{
    return p.val < q.val;
}

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

void update( int x , int num )
{
    while( x )
    {
        tree[x] += num;
        x -= lowbit(x);
    }
}

LL getSum( int x )
{
    LL sum = 0;
    while( x<=n )
    {
        sum += tree[x];
        x += lowbit(x);
    }
    return sum;
}
int main()
{
    cin.sync_with_stdio(false);
    LL k , ans;
    while( cin >> n >> k )
    {
        ans = 0;
        memset( tree , 0 , sizeof(tree) );
        for( int i = 1 ; i<=n ; i++ )
        {
            cin >> node[i].val;
            node[i].id = i;
        }   
        stable_sort( node+1 , node+n+1 , cmp );
        for( int i = 1 ; i<=n ; i++ )
        {
            arr[ node[i].id ] = i;
        }
        for( int i = 1 ; i<=n ; i++ )
        {
            update( arr[i]+1 , 1 );
            ans += ( getSum(arr[i]) );
        }
        cout << max( ans-k , (LL)0 ) << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
int n;
const int size = 100010;
struct data
{
    int id;
    int val;
}node[size];
int tree[size];
int arr[size];

bool cmp( const data p , const data q )
{
    return p.val < q.val;
}

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

void update( int x , int num )
{
    while( x<=n )
    {
        tree[x] += num;
        x += lowbit(x);
    }
}

LL getSum( int x )
{
    LL sum = 0;
    while( x )
    {
        sum += tree[x];
        x -= lowbit(x);
    }
    return sum;
}
int main()
{
    cin.sync_with_stdio(false);
    LL k , ans;
    while( cin >> n >> k )
    {
        ans = 0;
        memset( tree , 0 , sizeof(tree) );
        for( int i = 1 ; i<=n ; i++ )
        {
            cin >> node[i].val;
            node[i].id = i;
        }   
        stable_sort( node+1 , node+n+1 , cmp );
        for( int i = 1 ; i<=n ; i++ )
        {
            arr[ node[i].id ] = i;
        }
        for( int i = 1 ; i<=n ; i++ )
        {
            update( arr[i] , 1 );
            ans += ( i - getSum(arr[i]) );
        }
        cout << max( ans-k , (LL)0 ) << endl;
    }
    return 0;
}

today:

　　总要有荒唐的事 来完整你的人生

　　多活十年又如何

　　不过是八九十岁罢了

　　不能多活二十岁这一年