Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) D. Restore Permutation (樹狀數組）

題目連結：https://codeforces.com/contest/1208/problem/D

思路：倒着到處理給出的序列s[i],對于每個s[i]，假設目前位置填的數是t + 1，那麼在它前面有1----t 比它小，且1----t == s[i] ,是以模拟這個過程即可：對每個位置i，算出最小的t個數的和等于s[i] ,i位置應該填的數就是t + 1,可以用樹狀數組模拟這個過程。

代碼：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + 10;

typedef long long ll;

ll a[maxn] , b[maxn];

ll ans[maxn]; 
int n;

ll lowbit(ll x) {
	return x & -x;
}

void add(ll x ,ll d) {
	while(x <= n) {
		a[x] += d;
		x += lowbit(x);
	}
}

ll query(int x) {
	ll sum = 0;
	while(x > 0) {
		sum += a[x];
		x -= lowbit(x); 
	}
	return sum;
}




int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i++) {
		cin >> b[i];
		add(i , i);
	}	
	for(int i = n ; i >= 1 ; i-- ) {
		ll t = 0 , sum = 0;
		for(int j = 21 ; j >= 0 ; j--) {
			if((t + (1 << j) < n )&& sum + a[t + (1 << j)] <= b[i]) {
				t += (1 << j);
				sum += a[t];
			}
		}
		ans[i] = t + 1;
		t = t + 1;
		add(t,-t);
	}
	for(int i = 1 ; i <= n ; i++) {
		if(i > 1)cout << " ";
		cout << ans[i];
	}
	cout << "\n";
	return 0;
}