《算法竞赛进阶指南》0x42树状数组 POJ2182谜一样的牛 树状数组/倍增
标签：复杂度 ios pac 搜索 二进制 math void for 倍增
题目链接：https://www.acwing.com/problem/content/245/
题目给出一个长度为n-1的序列表示一个位置前面有多少个比他小，问这个序列是多少？这个序列是一个1-n的全排列。
通过从后向前扫描可知每个位置的编号，比如最后一个是an+1，这个位置在之后不考虑，然后从接下来存在的位置中找出第ai+1小的，可以表示成一个01串，将用过的变为0，求第k个1，这个问题就变成了求这个01序列的前缀和中第一个大于等于ai+1的，通过树状数组和二分搜索可以在O(log^2n)时间内求出一个结果，总的时间复杂度是O(nlog^2n)。
通过倍增算法的话，一次计算时间可以降为O(logn)。倍增算法中很好的利用了二进制的特性以及树状数组中的c[x]管理的是lowbit(x)长度的和，利用二进制位将a[i]分解并且通过最多log(a[i])次叠加计算出小于a[i]的最后一个位置。然后下一个位置就是a[i]的位置。
注意，倍增算法中，小于等于a[i]的最后一个位置不一定是大于等于a[i]的第一个位置。所以需要计算小于a[i]的最后一个位置。
代码1：
#include
#includeusing namespace std;
const int maxn = 100010;
int c[maxn];
int n;
int a[maxn];
int lowbit(int x){
return x&(-x);
}
void update(int x,int C){
while(xn){
c[x]+=C;
x+=lowbit(x);
}
}
int query(int x){
int ans=0;
while(x){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int num[maxn];
int main(){
cin>>n;
for(int i=2;i){
scanf("%d",&a[i]);
a[i]++;
}
a[1]=1;
for(int i=1;ilowbit(i);
for(int i=n;i;i--){
int l=1,r=n;
while(l//二分求第一个大于等于ai的前缀和
int mid=(l+r)>>1;
if(query(mid)>=a[i])r=mid;
else l=mid+1;
}
num[i]=l;
update(l,-1);
}
for(int i=1;i"%d\n",num[i]);
return 0;
}
代码2：
#include
#include
#includeusing namespace std;
const int maxn = 100010;
int c[maxn],a[maxn];
int lowbit(int x){return x&(-x);}
int n;
void update(int x,int C){
while(xn){
c[x]+=C;
x+=lowbit(x);
}
}
int h[maxn];
int main(){
cin>>n;
for(int i=2;i){
scanf("%d",&a[i]);
a[i]++;
}
a[1]=1;
int p[30];
p[0]=1;
for(int i=1;i25;i++)p[i]=p[i-1]1;//预存2次幂
for(int i=1;ilowbit(i);
int t=log(n)/log(2);//最大的2^t
for(int i=n;i;i--){
int sum=0,ans=0;//ans中存放的是二进制位,表示最后一个小于ai的位置
for(int j=t;j>=0;j--){
if(ans+p[j]a[i]){
sum+=c[ans+p[j]];
ans+=p[j];
}
}
h[i]=ans+1;
update(ans+1,-1);
}
for(int i=1;i"%d\n",h[i]);
return 0;
}
《算法竞赛进阶指南》0x42树状数组 POJ2182谜一样的牛 树状数组/倍增
标签：复杂度 ios pac 搜索 二进制 math void for 倍增
原文地址：https://www.cnblogs.com/randy-lo/p/13296455.html
评论