244. 谜一样的牛
- 题目
- 提交记录
- 讨论
- 题解
有n头奶牛，已知它们的身高为 1~n 且各不相同，但不知道每头奶牛的具体身高。
现在这n头奶牛站成一列，已知第i头牛前面有AiAi头牛比它低，求每头奶牛的身高。
输入格式
第1行：输入整数n。
第2..n行：每行输入一个整数AiAi,第i行表示第i头牛前面有AiAi头牛比它低。
（注意：因为第1头牛前面没有牛，所以并没有将它列出）
输出格式
输出包含n行，每行输出一个整数表示牛的身高。
第i行输出第i头牛的身高。
数据范围
1≤n≤1051≤n≤105
输入样例：
5
1
2
1
0
输出样例：
2
4
5
3
1分析：
这题算是树状数组的经典题目了。
这题的思想是维护一个长度为n的01前缀，如果为1说明位置没有被占，如果为0，说明位置备战。
我们倒着枚举a[i]，因为a[i]代表前面有多少头奶牛比他矮，，即前面有多少个1。所有我们要做的工作快速查找第a[i]+1的位置。
有两种方法：二分和倍增。
# include<cstdio>
# include<iostream>
# include<fstream>
# include<algorithm>
# include<functional>
# include<cstring>
# include<string>
# include<cstdlib>
# include<iomanip>
# include<numeric>
# include<cctype>
# include<cmath>
# include<ctime>
# include<queue>
# include<stack>
# include<list>
# include<set>
# include<map>
using namespace std;
typedef long long ll;
const int N = 100000 + 11;
const int mod = 1e9 + 7;
//树状数组只能计算A[1]开始的和，A[0]这个元素是不能用的。
const int MAXN=50000+5;//最大元素个数
int n;//元素个数
int a[MAXN];
int c[MAXN];//c[i]==A[i]+A[i-1]+...+A[i-lowbit(i)+1]
//返回i的二进制最右边1的值
int lowbit(int i)
{return i&(-i);
}
//返回A[1]+...A[i]的和
ll sum(int x)
{ll sum = 0;while(x){sum += c[x];x -= lowbit(x);}return sum;
}//令A[i] += val
void add(int x, ll val)
{while(x <= n) //注意这里的n，是树状数组维护的长度{c[x] += val;x += lowbit(x);}
}
//二分查询 第x个1的位置
int two_query(int x)
{int l=1,r=n;while(l<r){int mid=(l+r)>>1;if(sum(mid)>=x){r=mid;}elsel=mid+1;}return l;
}
//倍增查询第x个1的位置
ll p[100];
int lim;
void bz_init() //预处理2^n
{p[0] = 1;for (int i = 1; i < 20; i++) p[i] = p[i-1] << 1; lim=log(n)/log(2)+1;
}
int bz_query(int x)
{int ans=0,sum=0;for(int j=lim;j>=0;j--){if(ans+p[j]<=n&&sum+c[ans+p[j]]<x){sum+=c[ans+p[j]];ans+=p[j];}}return ans+1;}int ans[N];
int main()
{while(scanf("%d",&n)!=-1){memset(c,0,sizeof(c));add(1,1);for(int i=2; i<=n; i++){scanf("%d",&a[i]);add(i,1);}bz_init();for(int i=n; i>=1; i--){int pos=bz_query(a[i]+1);//询问第a[i]+1个1的位置在哪里add(pos,-1);ans[i]=pos;}for(int i=1; i<=n; i++){printf("%d\n",ans[i]);}}return 0;
}