Keep it Beautiful

题面翻译

定义一个序列为好, 当且仅当我们能从头开始选一段序列(长度可以为0, 相对顺序不变)放到尾部的后边, 由此得到的新序列是非递减的, 注意当序列为空时, 这个序列也是好序列

初始时序列为空, 然后给你 $q$ 个数字, 按次序询问你对于当前这个数 $x$ 如果放到当前这个序列的尾部, 是否会破坏当前序列的好性质, 如果会就不选, 不会就可以选然后放到序列尾部变成一个新序列

要我们输出 $q$ 个数, 对应询问, 如果这个数你选了, 那么对应位置就是1, 否则就是0

比如你选了第1个数, 其他都没选, 那么就输出 1000000....0

题目描述

The array $ [a_1, a_2, \dots, a_k] $ is called beautiful if it is possible to remove several (maybe zero) elements from the beginning of the array and insert all these elements to the back of the array in the same order in such a way that the resulting array is sorted in non-descending order.

In other words, the array $ [a_1, a_2, \dots, a_k] $ is beautiful if there exists an integer $ i \in [0, k-1] $ such that the array $ [a_{i+1}, a_{i+2}, \dots, a_{k-1}, a_k, a_1, a_2, \dots, a_i] $ is sorted in non-descending order.

For example:

$ [3, 7, 7, 9, 2, 3] $ is beautiful: we can remove four first elements and insert them to the back in the same order, and we get the array $ [2, 3, 3, 7, 7, 9] $ , which is sorted in non-descending order;
$ [1, 2, 3, 4, 5] $ is beautiful: we can remove zero first elements and insert them to the back, and we get the array $ [1, 2, 3, 4, 5] $ , which is sorted in non-descending order;
$ [5, 2, 2, 1] $ is not beautiful.

Note that any array consisting of zero elements or one element is beautiful.

You are given an array $ a $ , which is initially empty. You have to process $ q $ queries to it. During the $ i $ -th query, you will be given one integer $ x_i $ , and you have to do the following:

if you can append the integer $ x_i $ to the back of the array $ a $ so that the array $ a $ stays beautiful, you have to append it;
otherwise, do nothing.

After each query, report whether you appended the given integer $ x_i $ , or not.

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

Each test case consists of two lines. The first line contains one integer $ q $ ( $ 1 \le q \le 2 \cdot 10^5 $ ) — the number of queries. The second line contains $ q $ integers $ x_1, x_2, \dots, x_q $ ( $ 0 \le x_i \le 10^9 $ ).

Additional constraint on the input: the sum of $ q $ over all test cases does not exceed $ 2 \cdot 10^5 $ ).

输出格式

For each test case, print one string consisting of exactly $ q $ characters. The $ i $ -th character of the string should be 1 if you appended the integer during the $ i $ -th query; otherwise, it should be 0.

样例 #1

样例输入 #1

3
9
3 7 7 9 2 4 6 3 4
5
1 1 1 1 1
5
3 2 1 2 3

样例输出 #1

111110010
11111
11011

分析

我们先思考一下好序列有什么性质, 也就是说啥样的序列才可以通过把开头一段移到结尾实现非递减呢?

先声明下标从1开始

假设我们要把 1到p 这一段移到结尾, 那么新序列就是 a[p+1], a[p+2],...,a[n], a[1], a[2],..., a[p] , 如果满足非递减,

那么首先毫无疑问的是 a[p+1] 是最小值,
然后 p+1到n 和 1到p 这两段都是有非递减性质,
且 a[n] 应该小于等于 a[1]

然后我们就可以通过这个性质来面对 q 个询问了

注意: 是否会破坏好性质, 是对于当前还没加入这个数的序列而言的, 不是让你所有一起考虑然后问你怎么样可以得到最长的好序列的, 我们只需要关注当前即可

当序列为空的时候, 随便加进来什么数都不会破坏好性质, 所以第一个数我们一定会加入序列

依据性质2 这两段都要具有 非递减的单调性, 我们就可以来选数字了, 我们可以用 两个单调栈 来寻找正确答案, 一个栈代表 1到p 这一段记为 pre, 一个栈代表 p+1 到 n 这一段记为back

已知第一个数肯定要加入pre栈, 然后后边来的数如果大于等于pre栈栈顶元素, 就加入pre栈中, 直到遇到第一个小于pre栈栈顶元素的数, 那么毫无疑问, 这个数要放入back栈栈底, 然后pre栈就锁住了, 因为新来的只能放到序列尾部啊

在此之后, 入back栈的元素不仅要满足大于等于back栈栈顶, 还要满足性质3, 也即是小于pre栈栈顶

我们栈存的是结构体, 结构体包含这个数的数值以及位置, 输出的时候我们根据栈中元素的位置输出的是1, 其他就是0

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int prett, bktt;
int ans[N];
struct node
{
	int v, idx;
}pre[N], back[N];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t; cin >> t;
	while(t--)
	{
		prett = bktt = 0;	//多例清空 
		int n; cin >> n;
		for(int i = 1; i <= n; i++)
		{
			int a; cin >> a;
			if(i == 1)
			{
				pre[++prett].v = a, pre[prett].idx = i;
				continue;
			}
			
			if(!bktt) //如果后端栈为空 直接往前端塞 
			{
				if(a >= pre[prett].v) pre[++prett].v = a, pre[prett].idx = i;
				else if(a <= pre[1].v) back[++bktt].v = a, back[bktt].idx = i;
			}
			else	//如果后端栈不为空 不能再往前端栈塞了 
			{
				if(a >= back[bktt].v && a <= pre[1].v)  back[++bktt].v = a, back[bktt].idx = i;
			}
		}
		for(int i = 1; i <= prett; i++) ans[pre[i].idx] = 1;
		for(int i = 1; i <= bktt; i++) ans[back[i].idx] = 1;
		for(int i = 1; i <= n; i++) cout << ans[i];
		cout << endl;
		for(int i = 1; i <= n; i++) ans[i] = 0;	//多例清空
	}
}

JZTXT

CF1841B