#C240930A. Longest Max Min Subsequence

标签（Label）

单调栈
贪心

网址（Website）

Longest Max Min Subsequence - 洛谷

Problem - 2001D - Codeforces

题目（Problem）

题目描述

给你一个整数序列 $a_1,a_2,\ldots,a_n$ 。设 $S$ 是 $a$ 的所有可能的非空子序列的集合，且没有重复的元素。你的目标是找出 $S$ 中最长的序列。如果有多个序列，请找出将奇数位置上的项乘以 $-1$ 后，使词序最小的序列。

例如，给定 $a = [3, 2, 3, 1]$ ， $S = \{[1], [2], [3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 3, 1], [3, 2, 1]\}$。那么 $[2, 3, 1]$ 和 $[3, 2, 1]$ 将是最长的，而 $[3, 2, 1]$ 将是答案，因为 $[-3, 2, -1]$ 的词序小于 $[-2, 3, -1]$ 。

如果 $c$ 可以通过删除几个(可能是零个或全部)元素从 $d$ 得到，那么序列 $c$ 就是序列 $d$ 的子序列。

当且仅当以下条件之一成立时，序列 $c$ 在词法上小于序列 $d$ ：

$c$ 是 $d$ 的前缀，但 $c \ne d$ ；
在 $c$ 和 $d$ 不同的第一个位置，序列 $c$ 中的元素小于 $d$ 中的相应元素。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 5 \cdot 10^4$ )。测试用例说明如下。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 3 \cdot 10^5$ ) - $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le n$ ) - 序列 $a$ 。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$ 。

输出

对于每个测试用例，按以下格式输出答案：

在第一行输出整数 $m$ - $b$ 的长度。

然后在第二行输出 $m$ 个整数 $b_1, b_2, \ldots, b_m$ - 序列 $b$ 。

样例输入1

4
4
3 2 1 3
4
1 1 1 1
9
3 2 1 3 2 1 3 2 1
1
1

样例输出1

样例输入2

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

样例输出2

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

注

在第一个例子中， $S = {[1], [2], [3], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2], [2, 1, 3], [3, 2, 1]}$ 。其中， $[2, 1, 3]$ 和 $[3, 2, 1]$ 最长，而 $[-3, 2, -1]$ 比 $[-2, 1, -3]$ 的词性小，所以 $[3, 2, 1]$ 是答案。

在第二个例子中， $S = {[1]}$ ，所以 $[1]$ 是答案。

题解（Solution）

推荐一篇题解： Longest Max Min Subsequence - 洛谷专栏。

$\qquad$要让获得的序列奇数位最大，偶数为最小。我们先考虑让所有位最大的情况，发现直接维护一个单调递减的单调栈就可以解决问题。如果当前 $a[i]$ 在单调栈内，那么直接跳过（单调栈里面的一定是保证最优的）；如果不在，考虑弹出栈顶，注意如果这个 $a[i]$ 后面不会再出现，就不能删除，可以用一个 $lst$ 数组预处理解决这个问题。

$\qquad$考虑使用单调栈解决更复杂的问题，每次得到 $a[i]$ 的时候考虑和栈顶和栈的次顶比较，分类讨论所有情况，发现直接使用 $STL$ 包装的 $stack$ 难以获取第二位栈顶，直接换成 $vector$ 即可。

$\qquad$时间复杂度：$O(n)$ 。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 301234;
bool ST;

bitset<N> hav;
int n,a[N];

vector<int> st;
inline void out(int x){
	while(x--){
		hav[st.back()] = false;
		st.pop_back();
	}
}

int lst[N];
inline int solve(){
	st.clear(), hav.reset();
	For(i,1,n) lst[i] = 0;
	Rof(i,n,1) if(!lst[a[i]]) lst[a[i]] = i;
	For(i,1,n){
		if(st.empty()) st.emplace_back(a[i]),hav[a[i]]=true;
		if(hav[a[i]]) continue;
		while(st.size() >= 2){
			int c1 = *prev(st.end(),2), c2 = *prev(st.end());
			bool f = false;
			if(!f && i<lst[c1] && i<lst[c2]){
				if(st.size()&1) {if(a[i] < c1) out(2),f = true;}
				else 			{if(a[i] > c1) out(2),f = true;}
			}
			if(!f && i<lst[c2]){
				if(st.size()&1) {if(a[i] > c2) out(1),f = true;}
				else 			{if(a[i] < c2) out(1),f = true;}
			}
			if(!f) break;
		}if(st.size()==1 && i<lst[st.back()] && a[i]>st.back()) out(1);//判断只剩一个的情况 
		
		st.emplace_back(a[i]), hav[a[i]] = true;
	}return st.size();
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T=rd(),Tim = clock();
	while(T--){
		n = rd();For(i,1,n) a[i] = rd();
		printf("%lld\n",solve());
		for(auto i=st.begin();i!=st.end();i++){
			printf("%lld",*i);
			if(i!=prev(st.end())) printf(" ");//这个地方很逆天
		}printf("\n");
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}