学步园

大意略。

思路：倒序插入，表示从左往右数，第i个区间有多少个空位置，于是找到了最终的坐标。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN = 200010;

int n, id;
int Tree[MAXN<<2];
int pos[MAXN], val[MAXN];
int ans[MAXN];

void build(int o, int L, int R)
{
	int M = L+(R-L)/2;
	Tree[o] = R-L+1;
	if(L == R) return ;
	build(o*2, L, M);
	build(o*2+1, M+1, R);
}

void update(int p, int o, int L, int R)
{
	int M = L+(R-L)/2;
	Tree[o]--;
	if(L == R) id = L;
	else
	{
		if(p <= Tree[o*2]) update(p, o*2, L, M);
		else
		{
			p -= Tree[o*2];
			update(p, o*2+1, M+1, R);
		}
	}
}

void read_case()
{
	build(1, 1, n);
	for(int i = 1; i <= n; i++) scanf("%d%d", &pos[i], &val[i]);
	for(int i = n; i >= 1; i--)
	{
		update(pos[i]+1, 1, 1, n);
		ans[id] = val[i];
	}
}

void solve()
{
	read_case();
	for(int i = 1; i <= n; i++) printf(i != n? "%d ":"%d\n", ans[i]);
}

int main()
{
	while(~scanf("%d", &n))
	{
		solve();
	}
	return 0;
}