AcWing 244 谜一样的牛 (线段树)

https://www.acwing.com/problem/content/245/

线段树维护一个(01)序列，(b[i] = 1)表示身高为(i)的牛是否出现过，倒着扫一遍，
每次找到第(a[i] + 1)个(1)（未出现过的身高）就是当前牛的身高，并把该位置变成(0)
线段树上二分查找即可

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 100010;

int n; 
int a[maxn], b[maxn], cnt = 0;

struct SEG{
	int sum;
}t[maxn<<2];

void pushup(int i){t[i].sum = t[i << 1].sum + t[i << 1 | 1].sum;}

void build(int i, int l, int r){
	if(l == r){
		t[i].sum = 1;
		return;
	}
	
	int mid = (l + r) >> 1;
	build(i << 1, l, mid); build(i << 1 | 1, mid + 1, r);
	pushup(i);
}

void modify(int i, int l, int r, int p){
	if(l == r){
		t[i].sum -= 1;
		return;
	}
	
	int mid = (l + r) >> 1;
	if(p <= mid) modify(i << 1, l, mid, p);
	else modify(i << 1 | 1, mid + 1, r, p);
	pushup(i);
}

int find(int i, int l, int r, int k){
	if(l == r) return l;
	
	int mid = (l + r) >> 1;
	if(t[i << 1].sum >= k) return find(i << 1, l, mid, k);
	else return find(i << 1 | 1, mid + 1, r, k - t[i << 1].sum); 
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	n = read();
	for(int i = 2; i <= n ; ++i) a[i] = read();
	
	build(1, 1, n);
	
	for(int i = n ;i >= 1 ; --i){
		int H = find(1, 1, n, a[i] + 1);
		b[++cnt] = H;
		modify(1, 1, n, H);
	}
	
	for(int i = cnt ; i >= 1; --i){
		printf("%d
",b[i]);
	}
	
	return 0;
}