D. Permutation restoration (greedy / double pointer /set)

subject

The question

Given length is n Permutation a[i], Make b[i]=i/a[i]（ Rounding down ）, Now given b[i], Seek to restore the original a[i].
If there are multiple solutions , Output any set of , The problem ensures that there is at least one solution to the data .

Ideas

because $b[i]=i/a[i]$（ Rounding down ）, therefore
$a[i]\ast b[i]<=i<a[i]\ast (b[i]+1)$, therefore
$i/(b[i]+1)<a[i]<=i/b[i]$
Again because a[i] It's arrangement , We can enumerate every number from small to large , At the same time maintain Include the current number The range of ;
Every time you select an interval , choice The earliest expiration date Of , namely Right interval minimum the .

Combined with code understanding

Code

#include<bits/stdc++.h> 
using namespace std;
#define ll long long
const int maxn = 500010;

int n, m;
int a[maxn], b[maxn];
void solve() {
    
	scanf("%d", &n);
	vector<pair<int, int> > ve;
	for (int i = 1; i <= n; ++i) {
    
		scanf("%d", &b[i]);
		ve.push_back(make_pair(i/(b[i]+1)+1, i));
	}
	
	//  Left subscript of interval , Sort from small to large  
	sort(ve.begin(), ve.end());
// for (auto v: ve) {
    
// printf("{%d %d}\n", v.first, v.second);
// }
	set<pair<int, int> > st;
	for (int i = 1, j = 0; i <= n; ++i) {
    
		//  Will contain number i The interval of is crammed into the set  
		while (j < n && ve[j].first <= i) {
    
			int pos = ve[j].second;
			if(b[pos])
				st.insert(make_pair(pos/b[pos], pos));
			else
				st.insert(make_pair(n, pos));
			++j;
		}
		// debug 
		if (st.empty()) {
    
			printf("%d corrupt\n", i);
			break;
		}
		//  Select the one with the smallest right boundary from the set  
		a[st.begin()->second] = i;
		st.erase(st.begin());
	}
	
	for (int i = 1; i <= n; ++i) {
    
		printf("%d ", a[i]);
	}
	printf("\n");
	
}
int main() {
    
	int t;
	scanf("%d", &t);
	while (t--) {
    
		solve();
	}
}