题解 | 算法竞赛进阶指南 lost cow (3种做法)

题描述

有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;
}