树状数组板子题之一：poj 2299：Ultra-QuickSort（求逆序对）

题目链接：poj 2299:Ultra-QuickSort

其实看似是问快排的交换总次数
其实就是问逆序对的总数

开始实现不知道怎么搞，看了题解之后原来是要用到离散化，感觉有点神奇

代码入下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
/**主要用于离散化*/
struct Node
{
int val;
int pos;
}node[500010];
int c[500010];
int n;
inline int lowbit(int x)
{
return x&(-x);
}
int cmp(Node x,Node y)
{
if(x.val!=y.val)
return x.val<y.val;
else
return x.pos<y.pos;
}
/**由于求逆序对的的特殊性，只需要加一，于是就只要一个参数即可*/
void add(int x)
{
for(int i=x;i<=n;i+=lowbit(i))
{
c[i]++;
}
}
ll sum(int x)
{
ll s=0;
for(int i=x;i;i-=lowbit(i))
{
s+=c[i];
}
return s;
}
int main()
{
while(~scanf("%d",&n))
{
if(n==0)
break;
memset(node,0,sizeof(node));
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
scanf("%d",&node[i].val);
node[i].pos=i;
}
sort(node+1,node+n+1,cmp);
ll cnt=0;
for(int i=1;i<=n;i++)
{
add(node[i].pos);
cnt+=i-sum(node[i].pos);
}
printf("%lldn",cnt);
}
return 0;
}

最后

以上就是欢喜苗条最近收集整理的关于树状数组板子题之一：poj 2299：Ultra-QuickSort（求逆序对） 树状数组板子题之一：poj 2299：Ultra-QuickSort（求逆序对） 的全部内容，更多相关树状数组板子题之一：poj内容请搜索靠谱客的其他文章。