题目描述
有n头奶牛,已知它们的身高为 1~n 且各不相同,但不知道每头奶牛的具体身高。
现在这nn头奶牛站成一列,已知第i头牛前面有AiAi头牛比它低,求每头奶牛的身高。
输入格式
第1行:输入整数nn。
第2..n行:每行输入一个整数AiAi,第i行表示第i头牛前面有AiAi头牛比它低。
(注意:因为第1头牛前面没有牛,所以并没有将它列出)
输出格式
输出包含nn行,每行输出一个整数表示牛的身高。
第ii行输出第ii头牛的身高。
数据范围
1≤n≤105
样例
输入样例:
5
1
2
1
0
输出样例:
2
4
5
3
1
算法1
树堆
每次找第a[i] 大的数据 同时不能与后面出现的冲突
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fir first
#define sec second
const int maxn=1e5+10;
int siz[maxn];
int s[maxn][3];
int w[maxn],pos[maxn];
int tot;
void up(int i) {
siz[i]=siz[s[i][0]]+siz[s[i][1]]+1;
}
void spin(int &i,int p) {
int t=s[i][p];
s[i][p]=s[t][!p],s[t][!p]=i,up(i),up(t),i=t;
}
void ins(int x,int &i) {
if(!i) {
i=++tot,siz[i]=1,w[i]=x,pos[i]=rand();
return;
}
siz[i]++;
if(x<=w[i]) {
ins(x,s[i][0]);
if(pos[s[i][0]]<pos[i])spin(i,0);
} else {
ins(x,s[i][1]);
if(pos[s[i][1]]<pos[i])spin(i,1);
}
}
void del(int x,int &i) {
if(w[i]==x) {
if(s[i][0]*s[i][1]==0) {
i=s[i][0]+s[i][1];
return;
}
if(pos[s[i][0]]>pos[s[i][1]]) {
spin(i,1);
del(x,s[i][0]);
} else {
spin(i,0);
del(x,s[i][1]);
}
} else if(w[i]>x)del(x,s[i][0]);
else del(x,s[i][1]);
up(i);
}
int find(int x,int i) {
if(!i)return 1;
if(w[i]>=x)return find(x,s[i][0]);
return find(x,s[i][1])+siz[s[i][0]]+1;
}
int ask(int x,int i) {
if(siz[s[i][0]]==x-1)return w[i];
if(siz[s[i][0]]>=x)return ask(x,s[i][0]);
return ask(x-siz[s[i][0]]-1,s[i][1]);
}
int ans[maxn];
int a[maxn];
signed main() {
int n;
cin>>n;
int root=0;
ins(1,root);
for(int i=2; i<=n; i++) cin>>a[i],ins(i,root),a[i]++;
for(int i=n; i>1; i--) {
ans[i]=ask(a[i],root);
del(ans[i],root);
}
cout<<ask(1,root)<<endl;
for(int i=2; i<=n; i++) {
cout<<ans[i]<<endl;
}
return 0;
}
算法2
后面看主席树 觉得 权值线段树也能过去orz
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
const int maxn = 1e5 + 5;
int n, m;
int b[maxn << 2];
void push_up(int rt) {
b[rt] = b[rt << 1] + b[rt << 1 | 1] ;
}
void update(int L, int l, int r, int rt, int c) {
if(l == r) {
b[rt] += c;
return ;
}
int mid = l + r >> 1;
if(L <= mid) update(L, l, mid, rt << 1, c);
else update(L, mid + 1, r, rt << 1 | 1, c);
push_up(rt);
}
void query(int L, int l, int r, int rt) {
if(l == r) {
cout << l << " " << b[rt] << endl;
return ;
}
int mid = l + r >> 1;
if(L <= mid) query(L, l, mid, rt << 1);
else query(L, mid + 1, r, rt << 1 | 1);
}
int find_k(int l, int r, int rt, int k) {
if(l == r) {
return l;
}
int mid = l + r >> 1;
if(k <= b[rt << 1]) return find_k(l, mid, rt << 1, k);
else return find_k(mid + 1, r, rt << 1 | 1, k - b[rt << 1]);
}
int a[maxn];
int ans[maxn];
int main() {
fastio;
cin >> n;
for (int i = 1; i <= n; i ++) {
update(i, 1, n, 1, 1);
}
for(int i = 2; i <= n; i ++) {
cin >> a[i];
}
a[1] = 0;
int k = n;
for(int i = n; i >= 1; i --) {
ans[i] = find_k(1, n, 1, a[i] + 1);
// cout << find_k(1, n, 1, a[i] + 1) << endl;
// cout << "\\\\" << ans[i] << endl;
update(ans[i], 1, n, 1, -1);
// query(ans[i], 1, n, 1);
}
for(int i = 1; i <= n; i ++)
cout << ans[i] << endl;
return 0;
}
解法3
我听同学说了下 终于找到二分树状数组在搞什么了
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int c[maxn];
int n;
int query(int x){
int res = 0;
for(; x; x -= x&(-x)) res += c[x];
return res;
}
void add(int x, int y){
for(;x <= n; x += x & (-x)) c[x] += y;
}
int a[maxn];
int ans[maxn];
int main(){
cin >> n;
add(1, 1);
a[1] ++;
for(int i = 2; i <= n ; i ++ ) {
cin >> a[i]; a[i] ++;
add(i, 1);
}
for(int i = n; i >= 1; i -- ) {
int l = 1, r = n + 1;
while(r - l >= 1){
int mid = l + r >> 1;
if(query(mid) >= a[i]) r = mid;
else l = mid + 1;
}
ans[i] = l;
add(l, -1);
// for(int i = 1; i <= n; i ++ ) {
// cout << query(i) << " ";
// }cout << endl;
}
for(int i = 1; i <= n; i ++ ) {
cout << ans[i] << endl;
}
return 0;
}
### 强强
平衡树爷Orz
## 资瓷