转自http://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 15773 | Accepted: 5563 |
Description
by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
Source
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500005;
int c[maxn],n;//存树状数组,n表示点数,从-1-开始“important"
int aa[maxn];//存离散化后的数组
class node
{
public:
int val,order;
};
node in[maxn];//存原始数据
//树状数组的3个函数
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
{
c[i]+=val;
}
}
int getsum(int x)
{
int temp=0;
for(int i=x;i>=1;i-=lowbit(i))
{
temp+=c[i];
}
return temp;
}
bool cmp(node a,node b)
{
return a.val<b.val;
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
for(int i=1;i<=n;i++) {scanf("%d",&in[i].val);in[i].order=i;}
//离散化
sort(in+1,in+n+1,cmp);
for(int i=1;i<=n;i++) aa[in[i].order]=i;
//用树状数组求逆序数
memset(c,0,sizeof(c));
long long ans=0;
for(int i=1;i<=n;i++)
{
update(aa[i],1);
ans+=i-getsum(aa[i]);
}
cout<<ans<<endl;
}
return 0;
}
所以我们既可以修改x增大的路,求和x减小的路;也可以修改x减小的路,求和x增大的路,根据题目的需要来决定用哪种。我们只是将两个函数中的循环语句调换了下,现在每次要修改点x的值,就要修改(1, …x-Lowbit(x-Lowbit(x))), x-Lowbit(x), x)路径,而求和就变成求(x, x+Lowbit(x), x+Lowbit(x+Lowbit(x))),…)这条路径的点。而这不正好就是大于等于x的点的求和吗?
所以我们既可以修改x增大的路,求和x减小的路;也可以修改x减小的路,求和x增大的路,根据题目的需要来决定用哪种。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500005;
int c[maxn],n;//存树状数组,n表示点数,从-1-开始“important"
int aa[maxn];//存离散化后的数组
class node
{
public:
int val,order;
};
node in[maxn];//存原始数据
//树状数组的3个函数
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
for(int i=x;i>=1;i-=lowbit(i))//修改
{
c[i]+=val;
}
}
int getsum(int x)
{
int temp=0;
for(int i=x;i<=n;i+=lowbit(i))//修改
{
temp+=c[i];
}
return temp;
}
bool cmp(node a,node b)
{
return a.val<b.val;
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
for(int i=1;i<=n;i++) {scanf("%d",&in[i].val);in[i].order=i;}
//离散化
sort(in+1,in+n+1,cmp);
for(int i=1;i<=n;i++) aa[in[i].order]=i;
//用树状数组求逆序数
memset(c,0,sizeof(c));
long long ans=0;
for(int i=1;i<=n;i++)
{
update(aa[i],1);
ans+=getsum(aa[i])-1;//修改
}
cout<<ans<<endl;
}
return 0;
}
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 15773 | Accepted: 5563 |
Description
by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
Sample Input
5 9 1 0 5 4 3 1 2 3 0
Sample Output
6 0
Source
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500005;
int c[maxn],n;//存树状数组,n表示点数,从-1-开始“important"
int aa[maxn];//存离散化后的数组
class node
{
public:
int val,order;
};
node in[maxn];//存原始数据
//树状数组的3个函数
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
{
c[i]+=val;
}
}
int getsum(int x)
{
int temp=0;
for(int i=x;i>=1;i-=lowbit(i))
{
temp+=c[i];
}
return temp;
}
bool cmp(node a,node b)
{
return a.val<b.val;
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
for(int i=1;i<=n;i++) {scanf("%d",&in[i].val);in[i].order=i;}
//离散化
sort(in+1,in+n+1,cmp);
for(int i=1;i<=n;i++) aa[in[i].order]=i;
//用树状数组求逆序数
memset(c,0,sizeof(c));
long long ans=0;
for(int i=1;i<=n;i++)
{
update(aa[i],1);
ans+=i-getsum(aa[i]);
}
cout<<ans<<endl;
}
return 0;
}
所以我们既可以修改x增大的路,求和x减小的路;也可以修改x减小的路,求和x增大的路,根据题目的需要来决定用哪种。我们只是将两个函数中的循环语句调换了下,现在每次要修改点x的值,就要修改(1, …x-Lowbit(x-Lowbit(x))), x-Lowbit(x), x)路径,而求和就变成求(x, x+Lowbit(x), x+Lowbit(x+Lowbit(x))),…)这条路径的点。而这不正好就是大于等于x的点的求和吗?
所以我们既可以修改x增大的路,求和x减小的路;也可以修改x减小的路,求和x增大的路,根据题目的需要来决定用哪种。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500005;
int c[maxn],n;//存树状数组,n表示点数,从-1-开始“important"
int aa[maxn];//存离散化后的数组
class node
{
public:
int val,order;
};
node in[maxn];//存原始数据
//树状数组的3个函数
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
for(int i=x;i>=1;i-=lowbit(i))//修改
{
c[i]+=val;
}
}
int getsum(int x)
{
int temp=0;
for(int i=x;i<=n;i+=lowbit(i))//修改
{
temp+=c[i];
}
return temp;
}
bool cmp(node a,node b)
{
return a.val<b.val;
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
for(int i=1;i<=n;i++) {scanf("%d",&in[i].val);in[i].order=i;}
//离散化
sort(in+1,in+n+1,cmp);
for(int i=1;i<=n;i++) aa[in[i].order]=i;
//用树状数组求逆序数
memset(c,0,sizeof(c));
long long ans=0;
for(int i=1;i<=n;i++)
{
update(aa[i],1);
ans+=getsum(aa[i])-1;//修改
}
cout<<ans<<endl;
}
return 0;
}