CF1506 E Restoring the Permutation

知识点：STL、在线处理

题目链接

题意

给定一段序列所有前缀的最大值序列，求字典序最小和最大的原序列。

思路

思路简单，实现较难。易知给定序列单调不减，相邻不相同元素中右边的元素即为原序列的元素。（特别地第一个元素为原序列的元素）剩下的元素贪心地选择越大的数填在越前/后面，注意在一段元素全相等子串中对应原序列的每个元素都不能超过子串元素。
第一次尝试维护vis数组表示是否取用过，取用过则取更小的，TLE on test 10。
后发现从大到小、从前往后填数字的时候只需要找到未使用的数中第一个小于等于前一个数字的数字即可。故维护的数据结构需要支持单点查找、插入、删除，即set。

代码

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const ll N=2e5+10;
const ll mod=1e9+7;

ll n;
ll arr[N];

void solve()
{
   
	scanf("%lld",&n);
	for(ll i=1; i<=n; i++) scanf("%lld",&arr[i]);
	vector<ll> ans(n+10);
	set<ll> left;//未使用过的数字
	for(ll i=1; i<=n; i++) left.insert(i);
	for(ll i=1; i<=n; i++)
	{
   
		if(arr[i]!=arr[i-1])//找到分界点
		{
   
			ans[i]=arr[i];//填入右边的数
			left.erase(arr[i]);//从未使用过的数字中删除
		}
	}
	//带2表示处理字典序最大
	vector<ll> ans2(ans);
	set<ll> left2(left);
	for(ll i=1; i<=n; i++)
	{
   
		if(ans[i]) continue;
		ans[i]=*left.begin();//每次取最小
		left.erase(left.begin());
	}
	for(ll i=1; i<=n; i++)
	{
   
		if(ans2[i]) continue;
		auto p=--left2.upper_bound(ans2[i-1]);//第一个小于等于前一个数字的
		//数字的迭代器
		ans2[i]=*p;
		left2.erase(p);
	}
	for(ll i=1; i<=n; i++)
		printf("%lld ",ans[i]);
	puts("");
	for(ll i=1; i<=n; i++)
		printf("%lld ",ans2[i]);
	puts("");
}

int main()
{
   
	ll t;
	scanf("%lld",&t);
	while(t--)
		solve();
	return 0;
}