dp 部分好像有很多题解讲了，就不细讲了，首先易得结论每个数最终只会有三种情况 \(+\infty,-\infty\) 或是其本身。有状态 \(f_{i,v,t,L_1,L_2}\) 表示前缀 \(i\)，\(v=0/1\) 表示当前段是递增或递减，\(t=0/1/2\) 表示当前数最终状态，\(L_1\) 是当前整段的长度，\(L_2\) 是最后值相同的最长后缀长度。
状态数已经是 \(n^3\) 级别的，考虑优化。影响下一位拓展的元素是 \(v,t\)，考虑根据 \(i,v,t\) 给状态分类，状态间有很诡异的偏序关系。
- \(c\) 较小的状态更优。
一定能占用后面一个位置改为与单调性相反的 \(\infty\) 使得 \(L_1,L_2\) 重置为最小。
- 若 \(c\) 相同，则 \(L_1\) 较小的状态更优。
考虑情况存在两种状态 \((L_1,L_2),(L_1',L_2')\) 此时若下一位拓展符合原单调性，则两状态整段长度均为对应的 \(L_1+1\)，但是若不符合单调性，则变为对应的 \(L_2+1\)。原本以为此时仅依据 \(L_1\) 偏序会出问题。
实际上并不存在这种情况，考虑弱化问题最终序列 \(a\) 没有值域限制，则 \(+\infty,-\infty\) 可以视作无平段（值相同的后缀），显然平段只会对单调性变化时造成负面影响。有了此性质，对于上述的两个状态，显然前者的开头到后者的平端前的区间均操作过，则第二个状态前一位必定为 \(+\infty\) 或 \(-\infty\)。则 \(L_1'=L_2'+1\) 故不存在该情况。
- 若前两者相同，则 \(L_2\) 较小状态更优。
显然，否则被完全偏序。
若 \(a\) 最终有值域限制，发现对于原来的 \(+\infty,-\infty\) 段，改为 \(\text{max},\text{max}-1\) 交替显然更优，后者同理，于是值域限制解决了。记录转移路径得到构造方案。
Takanashi Rikka
#include<bits/stdc++.h>
using namespace std;
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ve vector
#define intz(x,y) memset((x),(y),sizeof((x)))
template<typename Type>il void cmx(Type &x,Type y){if(y>x)x=y;}
template<typename Type>il void cmn(Type &x,Type y){if(y<x)x=y;}
#define lowbit(x) (x&-x)
#define pcount(x) __builtin_popcountll(x)
#define int ll
const int N=1e6+5,inf=1e9;
int a[N],MX=100000,MN=0;
struct node{int c,l1,l2,prev,pret;bool operator<(node x){return c^x.c?c<x.c:(l1^x.l1?l1<x.l1:l2<x.l2);}
}f[N][2][3];
il void cmn(node &x,node y,int v,int t){if(y<x)x=y,x.prev=v,x.pret=t;}
il int get(int x,int op){return op==0?MN:(op==1?MX:x);}
void UesugiErii(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];//0-up 1-dw//0-(-inf) 1-(inf) 2 -0for(int i=0;i<=n;i++)for(int j:{0,1})for(int k:{0,1,2})f[i][j][k]={inf,inf,inf};f[0][0][1]={0,0,0};for(int i=0;i<n;i++){for(int j:{0,1})for(int k:{0,1,2}){if((j==1&&k==1)||(!j&&!k))continue;node tmp=f[i][j][k];if((j==0?tmp.l1:tmp.l2)+1<m)cmn(f[i+1][0][1],{tmp.c+1,(j==0?tmp.l1:tmp.l2)+1,1},j,k);if((j==1?tmp.l1:tmp.l2)+1<m)cmn(f[i+1][1][0],{tmp.c+1,(j==1?tmp.l1:tmp.l2)+1,1},j,k);int fl=(a[i+1]==get(a[i],k)?j:a[i+1]<get(a[i],k));if((j==fl?tmp.l1:tmp.l2)+1<m)cmn(f[i+1][fl][2],{tmp.c,(j==fl?tmp.l1:tmp.l2)+1,k<2?1:(a[i+1]==a[i]?tmp.l2+1:1)},j,k);}}int ans=inf,idv=0,idt=0;for(int j:{0,1})for(int k:{0,1,2}){if((j==1&&k==1)||(!j&&!k))continue;if(f[n][j][k].c<ans)ans=f[n][j][k].c,idv=j,idt=k;}cout<<ans<<'\n';stack<int>z;for(int i=n,tv,tt;i;i--){z.push(get(a[i],idt)),tv=f[i][idv][idt].prev,tt=f[i][idv][idt].pret;if(tt==idt)MX=(MX==100000?99999:100000),MN=(MN==0?1:0);else MX=100000,MN=0;idv=tv,idt=tt;}while(z.size())cout<<z.top()<<' ',z.pop();cout<<'\n';
}
signed main(){//IO();cfast;int _=1,cas;//cin>>cas>>_;for(;_;_--)UesugiErii();return 0;
}