[POI2010] MOT-Monotonicity 2
题目描述
This task is a harder version of task Monotonicity from the third stage of 17th Polish OI. It wasn't used in the contest itself.
For an integer sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.1.png) we define its monotonicity scheme as the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.2.png) of symbols ![](http://main.edu.pl/images/OI17/mot-en-tex.3.png), ![](http://main.edu.pl/images/OI17/mot-en-tex.4.png) or ![](http://main.edu.pl/images/OI17/mot-en-tex.5.png).
The symbol ![](http://main.edu.pl/images/OI17/mot-en-tex.6.png) represents the relation between ![](http://main.edu.pl/images/OI17/mot-en-tex.7.png) and ![](http://main.edu.pl/images/OI17/mot-en-tex.8.png).
For example, the monotonicity scheme of the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.9.png) is ![](http://main.edu.pl/images/OI17/mot-en-tex.10.png).
We say that an integer sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.11.png) with monotonicity scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.12.png), realizes another monotonicity scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.13.png) if for every ![](http://main.edu.pl/images/OI17/mot-en-tex.14.png) it holds that ![](http://main.edu.pl/images/OI17/mot-en-tex.15.png).
In other words, the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.16.png) can be obtained by repeating the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.17.png) and removing appropriate suffix from that repetition.
For example, the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.18.png) realizes each and every one of the following schemes:
![](http://main.edu.pl/images/OI17/mot-en-tex.19.png) ![](http://main.edu.pl/images/OI17/mot-en-tex.20.png) ![](http://main.edu.pl/images/OI17/mot-en-tex.21.png) ![](http://main.edu.pl/images/OI17/mot-en-tex.22.png) as well as many others.
An integer sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.23.png) and a monotonicity scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.24.png) are given.
Your task is to find the longest subsequence ![](http://main.edu.pl/images/OI17/mot-en-tex.25.png) (![](http://main.edu.pl/images/OI17/mot-en-tex.26.png)) of the former that realizes the latter.
给出N个正整数a[1..N],再给出K个关系符号(>、<或=)s[1..k]。
选出一个长度为L的子序列(不要求连续),要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。
求出L的最大值。
感谢@cn:苏卿念 提供spj
输入输出格式
输入格式
The first line of the standard input holds two integers ![](http://main.edu.pl/images/OI17/mot-en-tex.27.png) and ![](http://main.edu.pl/images/OI17/mot-en-tex.28.png) (![](http://main.edu.pl/images/OI17/mot-en-tex.29.png), ![](http://main.edu.pl/images/OI17/mot-en-tex.30.png)), separated by a single space, denoting the lengths of the sequences ![](http://main.edu.pl/images/OI17/mot-en-tex.31.png) and monotonicity scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.32.png) respectively.
The second input line gives the sequence ![](http://main.edu.pl/images/OI17/mot-en-tex.33.png), i.e, it holds ![](http://main.edu.pl/images/OI17/mot-en-tex.34.png) integers ![](http://main.edu.pl/images/OI17/mot-en-tex.35.png) separated by single spaces (![](http://main.edu.pl/images/OI17/mot-en-tex.36.png)).
Finally, the third lines gives the monotonicity scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.37.png), i.e., it holds ![](http://main.edu.pl/images/OI17/mot-en-tex.38.png) s…
输出格式
In the first line of the standard output your program should print out a single integer ![](http://main.edu.pl/images/OI17/mot-en-tex.40.png), the maximum length of a subsequence of ![](http://main.edu.pl/images/OI17/mot-en-tex.41.png) that realizes the scheme ![](http://main.edu.pl/images/OI17/mot-en-tex.42.png).
In the second line it should print out any such subsequence ![](http://main.edu.pl/images/OI17/mot-en-tex.43.png), separating its elements by single spaces.
输入输出样例
输入样例 #1
7 3
2 4 3 1 3 5 3
< > =
输出样例 #1
6
2 4 3 3 5 3
说明
$1 \le n \le 500000$,$1 \le k \le 500000$,$1 \le a_i \le 10^6$,$s_j \in \{<, >, =\}$