自动搬运

查看原文

来自洛谷，原作者为

	q234rty **

搬运于2025-08-24 21:49:39，当前版本为作者最后更新于2019-02-10 22:41:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

安利窝的博客

相信很多人看到这道题的第一反应和窝一样：这不是水题吗，只要记 $f(i)$ 表示下标以 $i$ 结尾的最长合法子序列长度，转移树状数组优化一下就行了。

还有一些人可能觉得这道题需要在状态中记录长度 $\bmod k$，于是得到了优秀的 $O(nk\log n)$ 或 $O(nk)$ 做法。

第一反应觉得这道题是水题之后可能会觉得不对劲，DP 需要最优子结构，而这个 DP 看起来并不满足呀。

然而，这个 DP 确实是满足最优子结构的，为什么呢？

（网上的题解大都没写证明，neither_nor 写了证明但窝看不懂，于是窝决定写一下用谷歌翻译看波兰文官方题解（在 P152）的成果）

就是要证下标以 $i$ 结尾的最长合法子序列，一定可以由某个下标以 $j<i$ 结尾的最长合法子序列接上 $i$ 得到。

不失一般性，设下标以 $n$ 结尾的最长合法子序列第一个不满足这个条件，再设 $m$ 为这个子序列的上一个下标。

设 $b_1,b_2,\cdots,b_{f(m)}$ 为下标以 $m$ 结尾的最长合法子序列对应的下标序列，显然 $b_{f(m)}=m$，设 $k=f(n)$。

因为 $n$ 继承的不是 $m$ 的最优解，所以 $k-1<f(m)$，即 $f(m)\geq k$。

讨论：

• $a_m=a_n$，这时 $b_1,b_2,\cdots,b_{f(m)-1},n$ 长度为 $f(m) \geq k$，显然为一个不会更劣的解。
• $a_m<a_n$，这就是说 $s_{k-1}=``<"$，继续讨论：
  • $a_{b_{k-1}}<a_n$，那么 $b_1,b_2,\cdots,b_{k-1},n$ 长度为 $k$，不会更劣。
  • $a_{b_{k-1}}\geq a_n$，我们有 $a_{b_{k-1}}<a_{b_k}$，但是 $a_{b_{k-1}}\geq a_n>a_m$，也即一定存在一个 $w\geq k$ 满足 $a_{b_w}>a_{b_{w+1}}$，也即 $s_{w}=``>"$，我们取第一个这样的 $w$，于是 $\forall i \in [k,w), a_{b_i}\leq a_{b_{i+1}}$，又 $a_{b_{k-1}}<a_{b_k}$，于是 $a_{b_w}>a_{b_{k-1}}\geq a_n$，于是 $b_1,b_2,\cdots,b_{w},n$ 长度为 $w+1>k$，更优。
• $a_m>a_n$，同理得证。

这样就证完啦。

使用两个树状数组分别维护下一个是大于和小于的情况，等于直接用数组维护。

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

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
	#ifdef LOCAL
		freopen("3009.txt","r",stdin);
	#endif
	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
	bufpos=0;
}
#if NEG
int readint(){
	bool isneg;
	int val=0;
	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
	bufpos+=(isneg=buf[bufpos]=='-');
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return isneg?-val:val;
}
#else
int readint(){
	int val=0;
	for(;!isdigit(buf[bufpos]);bufpos++);
	for(;isdigit(buf[bufpos]);bufpos++)
		val=val*10+buf[bufpos]-'0';
	return val;
}
#endif
char readchar(){
	for(;isspace(buf[bufpos]);bufpos++);
	return buf[bufpos++];
}
int readstr(char* s){
	int cur=0;
	for(;isspace(buf[bufpos]);bufpos++);
	for(;!isspace(buf[bufpos]);bufpos++)
		s[cur++]=buf[bufpos];
	s[cur]='\0';
	return cur;
}
const int maxn=1000002;
inline void tense(pii &x,pii y){
	if (x<y)
		x=y;
}
struct bit{
	int n;
	pii t[maxn];
	void add(int p,pii v){
		for(;p<=n;p+=p&-p)
			tense(t[p],v);
	}
	pii query(int p){
		pii ans;
		for(;p;p-=p&-p)
			tense(ans,t[p]);
		return ans;
	}
}b1;
struct tib{
	int n;
	pii t[maxn];
	void add(int p,pii v){
		for(;p;p-=p&-p)
			tense(t[p],v);
	}
	pii query(int p){
		pii ans;
		for(;p<=n;p+=p&-p)
			tense(ans,t[p]);
		return ans;
	}
}b2;
inline pii inc(pii x){
	x.first++;
	return x;
}
int a[maxn],dp[maxn],lst[maxn],stk[maxn];
pii qwq[maxn];
char s[maxn];
int main(){
	init();
	int n=readint(),k=readint();
	for(int i=1;i<=n;i++)
		a[i]=readint();
	for(int i=1;i<=k;i++)
		s[i]=readchar();
	b1.n=b2.n=maxn-1;
	int ans=0;
	for(int i=1;i<=n;i++){
		pii lol;
		tense(lol,inc(b1.query(a[i]-1)));
		tense(lol,inc(b2.query(a[i]+1)));
		tense(lol,inc(qwq[a[i]]));
		dp[i]=lol.first,lst[i]=lol.second;
		// printf("dp[%d]=%d lst[%d]=%d\n",i,dp[i],i,lst[i]);
		lol.second=i;
		char now=s[(dp[i]-1)%k+1];
		if (now=='=')
			tense(qwq[a[i]],lol);
		else if (now=='<')
			b1.add(a[i],lol);
		else b2.add(a[i],lol);
		// printf("dp[%d]=%d lst[%d]=%d\n",i,dp[i],i,lst[i]);
		if (dp[i]>dp[ans])
			ans=i;
	}
	printf("%d\n",dp[ans]);
	int cur=0;
	while(ans){
		stk[++cur]=ans;
		ans=lst[ans];
	}
	for(int i=cur;i;i--)
		printf("%d ",a[stk[i]]);
}