7.6+7.7训练日记

休息好真的很重要,在家没人管都睡得太晚了,醒来自制力又不足,罪过.
第一题
首先在构造的答案排列 b b b中,有一个位置是一定与原序列一致的,
那就是 b p 0 b_{p_0} bp0​​,因为起始的Mex值要是1.
然后考虑扩展该结论,我们找到原数组0与1的位置 p 0 , p 1 p_0,p_1 p0​,p1​.
考虑下1是否能移动,可以发现,该情况下无论1朝着远离0的方向移动还是靠近0的方向移动,都会至少导致一个区间的Mex值与原数组不一致.所以此时0与1都不能移动.
接下来考虑2的位置 p 2 p_2 p2​,如果 p 2 介 于 [ p 0 , p 1 ] p2介于[p_0,p_1] p2介于[p0​,p1​]中,那么2可以放置的位置是
p 1 − p 0 + 1 − 2 p1-p0+1-2 p1−p0+1−2.如果 p 2 介 于 ( p 1 , n ) 中 p2介于(p1,n)中 p2介于(p1,n)中,结论与仅有0与1时情况一致,不过是此时的0是 [ p 0 , p 1 ] 区 间 [p_0,p_1]区间 [p0​,p1​]区间,1是此时的2.结论就是此时的2不能放置到其他位置,同理 p 2 介 于 ( 1 , p 0 ) 时 是 一 致 的 p2介于(1,p_0)时是一致的 p2介于(1,p0​)时是一致的
把该结论推广,我们知道了当前维护的区间就是考虑0~i-1形成的答案.此时考虑数字 i i i对答案的影响,就是放到哪里.在区间内,就可以随便在区间内放置(不能打乱之前i-1个数字放置的位置),否则,就只能放在原地,并且使得区间扩展.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--){
		int n;cin>>n;
		vector a(n),pos(n);
		for(int i=0;i>a[i];
		for(int i=0;is;
	string t;
	string ans;
	for(int i=1;i