poj 2299 Ultra-QuickSort 树状数组

求逆序对数,树状数组

数据范围较大,要离散化。

给每一个数据一个id, 第i个数据的id为i。 然后从小到大排序,对于每个id做 ans += read(n) - read(array[i].id),read(n) - read(array[i].id)表示原来在当前数的后面(其id大于当前数的id),
现在在当前数前面的数个数,也就是逆序对数。


#include<iostream>
#include
<cstring>
#include
<cstdio>
#include
<algorithm>
using namespace std;
const int MAXVAL = 500005;

int tree[MAXVAL] ;
struct Type
{
    
int num, id;
};

int n;
Type array[MAXVAL];

void update(int idx, int inc)  //更新idx的频率
{
    
while(idx <= n)
    {
        tree[idx] 
+= inc;
        idx 
+= (idx & - idx);
    }
}

int read(int idx)   //读取1--idx的频率和
{
    
int sum = 0;
    
while(idx > 0)
    {
        sum 
+= tree[idx];
        idx 
-= (idx & - idx);
    }
    
return sum;
}

int readSingle(int idx) // 读取某个位置的频率, O(lg MAXVAL)
{
     
int sum = tree[idx];
     
if(idx > 0)
     {
         
int z = idx - ( idx & - idx);  
         
         idx 
--;

         
while( idx != z)
         {
              sum 
-= tree[idx];

              idx 
-= (idx & - idx);
         }
     }

     
return sum;
}


bool cmp(const  Type &a, const Type &b)
{
    
return a.num < b.num;
}
int main()
{
    
while (scanf("%d",&n)  && n != 0)    
    {
        memset(array, 
0sizeof (array));
        memset(tree, 
0sizeof tree);

        
// read the data
        for(int i = 1; i <= n; i ++)
        {
            scanf(
"%d",&array[i].num);
            array[i].id 
= i;
        }
    
        sort(array 
+ 1, array + 1 + n, cmp);

        
long long ans = 0;
        
for(int i = 1; i <= n; i ++)
        {
            
//printf( "cal   %d \n",read(n) - read(array[i].id));
            ans += read(n) - read(array[i].id);
            update(  array[i].id, 
1);
        }
            
        cout 
<< ans << endl;
    }


    
return 0;
}

posted on 2011-03-16 20:49 田兵 阅读(235) 评论(2)  编辑 收藏 引用 所属分类: 数据结构

评论

# re: poj 2299 Ultra-QuickSort 树状数组 2011-04-12 09:25 银志圆

排序用sort不太妥当吧 sort是不稳定排序 如果给定的序列存在多个相同的元素会出现错误吧 尽管这个程序oj上能ac。
大概oj上给定的数据是互不相同的吧   回复  更多评论   

# re: poj 2299 Ultra-QuickSort 树状数组 2011-04-19 21:27 田兵

有个id, id小的在前面  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年4月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜