原题面：https://atcoder.jp/contests/wtf22-day2/tasks/wtf22_day2_b
题面翻译：
一个长度为 \(n\) 的排列 \(p\)，每次可以把一个长 \(k\) 区间的最大与次大值交换，问操作任意次数后可以得到的排列数量对 \(998244353\) 取模。
这题被我搬到了一场多校联考中。在搬到的题面中，我加入了 \(p_i=i\) 的 Subtask 以及 \(p\) 先增后减的 Subtask。这两个 Subtask 有助于我们去理解这题的做法。
-
\(p_i=i\)
或许你可以通过打表发现答案很有规律。但是为了做出正解我们可以在这档 Subtask 做出一些分析。
考虑从小往大分析每个数最终可以出现在什么位置。对于 \(1\le i\le k-2\)，最终一定有 \(p_i=i\)。而通过模拟一些简单的情况，我们发现对于 \(x\)，其能到达的最右侧的位置满足 \(r_x=\min(n,r_{x-k+2}+k-1)\)。并且，我们可以通过不断操作，让自己可以出现在 \([k-1,r_x]\) 的任意位置。
考虑去证明一下这件事情。归纳证明，假设目前对于 \(i-1\)，满足上述条件，且对于任何 \(\in[i,r_{i-1}]\) 的数都可以自由安排在 \([k-1,r_{i-1}]\) 的剩余的任何位置，且使用的操作区间的右端点都 \(\le r_{i-1}\)。现在归纳证明 \(i\) 的情况。首先，我们一定可以不断借 \([i-k+2,i-1]\) 这些数，与 \(i\) 一起往右推，直到这些数中有数不能再往右走了。容易证明这样得到的 \(r_i\) 可以用上述式子表示。然后考虑 \(>i\) 的数。我们考虑在把 \(r_i\) 往右推的过程中，进一步进行规约：假如 \(r_i\le k\) 时满足，那么可以把想要换到 \(k+1\) 上的数 \(x\)（\(x\ge i\)）换到 \(r_i\) 上，然后使得 \([i-k+2,i-1]\) 的数在上述位置上，然后通过一次右端点为 \(k+1\) 的交换操作把 \(k+1\) 换到 \([1,k]\) 内，$x $ 换到 \(k+1\) 上，那么就能使 \(r_i=k+1\) 时满足了。（其实和挪 \(i\) 的过程是类似的）。
-
\(p\) 先减后增的 Subtask
我们考虑从 \(p_i=i\) 推广到 \(p\) 先减后增。具体而言，令 \(q_i\) 表示 \(i\) 在最终排列中的位置，现在每个数 \(i\) 都有一个区间 \([l_i,r_i]\)，那么使得任意满足 \(q_i\in[l_i,r_i]\) 的 \(q\) 都可以得到。并且，满足 \([l_i,r_i]\subseteq [l_{i+1},r_{i+1}]\)，于是我们就可以从 \([l_i,r_i]\) 去往左往右拓展到 \([l_{i+1},r_{i+1}]\)。归纳证明的过程与 \(p_i=i\) 类似，只是多了 \(l_i\) 向左扩展和 \(r_i\) 向右扩展的步骤，且每次扩展（以 \(r_i\) 向右扩展举例），需要在让 \([l_i,r_i]\) 区间中的小的数尽可能往右靠的同时，让 \([r_i+1,n]\) 区间中的小的数尽可能向左靠，然后完成一次交换让 \(r_i\) 加一。
扩展的方法和正常情况区别不大。于是和正常情况放一起写。
-
正常情况
考虑把上一个 Subtask 的做法推广到一般情况。容易发现，唯一的区别其实就是变成了一个树形结构。这不会影响我们的做法。
具体而言，我们可以通过以下方法得到 \([l_i,r_i]\)：\(i\) 从小到大去扩展 \([l_i,r_i]\)。举扩展 \(r\) 为例。每次，根据前面的推导，我们可以将 $r_i $ 的初始值设为目前最大的包含 \(r_i\) 的区间的 \(r_i\)。然后我们再考虑能否向右移。我们维护两个 set \(s_1,s_2\) 表示如果目前的数都尽可能靠左/右填，那么还能空余哪些位置。有了这个，我们就能快速知道是否可以向右移了。
代码：
//vanitas vanitatum et omnia vanitas
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=2.5e5+5,mod=998244353;
int n,k,p[N],q[N],nxt[N],pre[N],l[N],r[N],pl[N],pr[N],s[N],ans=1;
set<int> sl,sr;
int findp(int x) {return x==pre[x]?x:pre[x]=findp(pre[x]);}
int findn(int x) {return x==nxt[x]?x:nxt[x]=findn(nxt[x]);}
int Pre(int x) {return findp(x-1);}
int Nxt(int x) {return findn(x+1);}
void del(int x) {pre[x]=Pre(x), nxt[x]=Nxt(x);}
int lb(int x) {return x&-x;}
void add(int x) {for(;x<=n;x+=lb(x)) s[x]++;}
int qry(int x,int y=0) {for(;x;x-=lb(x)) y+=s[x]; return y;}
bool ext(int x) {
int l=*prev(sr.find(x)), r=*next(sl.find(x));
return r-l-1>=k;
}
int tpl(int l) {return *sl.lower_bound(l);}
int tpr(int r) {return *prev(sr.upper_bound(r));}
void updl(int x) {
if(pl[x]) sl.insert(pl[x]);
pl[x]=tpl(l[x]); sl.erase(pl[x]);
}
void updr(int x) {
if(pr[x]) sr.insert(pr[x]);
pr[x]=tpr(r[x]); sr.erase(pr[x]);
}
bool extendl(int x) {
if(l[x]>1&&ext(l[x]-1)) {
--l[x]; del(l[x]);
updl(x); return 1;
} return 0;
}
bool extendr(int x) {
if(r[x]<n&&ext(r[x]+1)) {
++r[x]; del(r[x]);
updr(x); return 1;
} return 0;
}
signed main() {
n=read(), k=read();
rep(i,1,n) p[i]=read(), q[p[i]]=i;
rep(i,0,n+1) nxt[i]=pre[i]=i;
rep(i,0,n+1) sl.insert(i), sr.insert(i);
rep(i,1,n) {
l[i]=r[i]=q[i]; del(q[i]);
for(;;) {
int nl=Pre(l[i])+1, nr=Nxt(r[i])-1;
l[i]=nl, r[i]=nr; updl(i), updr(i);
bool gl=extendl(i), gr=extendr(i);
if(!gl&&!gr) break;
}
}
rep(i,1,n) {
int cc=r[i]-l[i]+1-(qry(r[i])-qry(l[i]-1));
ans=ans*cc%mod, add(r[i]);
}
printf("%lld\n",ans);
return 0;
}