【2023NOI模拟赛11】白 做题记录

你有一个 $1,2,\dots N$ 的排列 $P$。

你可以进行一次如下操作：选择一个非负整数 $k$，以及 $k$ 个不交的区间 $1\le l_1<r_1<l_2<r_2<\dots<l_k<r_k\le N$，然后对每个 $1\le i\le k$ 的 $i$，将 $P_{l_i},P_{l_i+1},P_{l_i+2},\dots,P_{r_i}$ 替换为它们的升序排列。

你想知道 $P$ 在操作完后可能有多少种不同的情况。由于情况数可能很多，所以你只想得到其对 $998244353$ 取模后的结果。请你帮帮你自己求出答案！

$1\le N\le 2\times 10^5$。

考虑设 $dp_{i}$ 表示 $P_{[1,i]}$ 在操作之后有多少种不同的情况，考虑转移。一个区间 $[l,r]$ 只能通过操作 $[l,r]$ 来排序当且仅当不存在 $k$ 满足 $l\le k\le r-1$ 且排序 $[l,k]$ 再排序 $[k+1,r]$ 得到的序列和排序 $[l,r]$ 相同。不妨称满足条件的区间是 ”好的“

那么设 $S_i$ 表示所有满足 $[j,i]$ 是好的的 $j$ 的集合，那么有转移 $dp_i=\sum\limits_{j\in S_i}dp_{j-1}$，初始状态 $dp_0=1$。

考虑求解 $S_i$，显然有一个 $O(n^2)$ 的算法：

对于每个 $i$，从 $i$ 开始往前遍历，并维护当前 $S_i$ 中最长的区间 $[l,i]$ 和其中的最小值 $val$。刚开始 $S_i=\{i\},l=i,val=a_i$，每遍历到一个位置 $j$：

• 若 $P_j<val$，什么也不做；
• 若 $P_j>val$，表明排序 $[j,i]$ 之后会有一些 $[l,i]$ 中的元素跑到 $P_j$ 前面，由于 $[l,i]$ 已经是好的了，所以这是排序 $[j,x]$ 再排序 $[x+1,i]$ 所做不到的，那么更新 $l=j$，并把 $j$ 加入 $S_i$，更新 $val$；

观察到许多 $S_i$ 是有大量重复的，考虑利用这种高重复性优化时间复杂度。设 $x$ 为满足 $P_x<P_i$ 且 $x<i$ 的最大的 $x$，$y$ 为满足 $P_y>P_i$ 且 $y<x$ 的最大的 $y$。那么有 $[x+1,i]\in S_i$ 且 $[y+1,x]\notin S_i$。

更进一步，设 $z$ 为 $[y+1,x]$ 中最小值的位置，由于 $P_y>P_i,P_i>P_x,P_x\ge P_z$，所以有 $P_z<P_y$，那么有 $[y+1,z]\in S_z$。并且观察到从 $i$ 和从 $z$ 开始遍历到 $y$ 时都有 $l=y,val=P_z$，所以 $S_z-[y+1,z]+[x+1,i]=S_i$。

那么二分 + ST 表找到 $x,y,z$，拿个前缀和维护转移即可。时间复杂度 $O(n\log n)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=200005,BS=20;
const int p=998244353;

int n,a[S];
int tot,sta[S],premn[S];
int mlog[S],mn[S][BS+5],mx[S][BS+5];
int sum[S],dp[S];

inline int quemn(int l,int r)
{
	int k=mlog[r-l+1];
	int x=mn[l][k],y=mn[r-(1<<k)+1][k];
	return a[x]<a[y]?x:y;
}

inline int quemx(int l,int r)
{
	int k=mlog[r-l+1];
	int x=mx[l][k],y=mx[r-(1<<k)+1][k];
	return a[x]>a[y]?x:y;
}

inline int fnd(int x,int val)
{
	int l=1,r=x,res=0;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(a[quemx(mid,x)]>val) res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}

inline int quesm(int l,int r)
{
	return (sum[r]-(l==0?0:sum[l-1])+p)%p;
}

int main()
{
	freopen("bai.in","r",stdin);
	freopen("bai.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sta[tot=0]=0;
	for(int i=1;i<=n;i++)
	{
		while(tot>0&&a[sta[tot]]>a[i]) tot--;
		premn[i]=sta[tot];
		sta[++tot]=i;
	}
	mlog[0]=-1;
	for(int i=1;i<=n;i++) mlog[i]=mlog[i>>1]+1,mn[i][0]=mx[i][0]=i;
	for(int j=1;j<=mlog[n];j++)
	{
		for(int i=1;i<=n-(1<<j)+1;i++)
		{
			int x=mn[i][j-1],y=mn[i+(1<<j-1)][j-1];
			mn[i][j]=a[x]<a[y]?x:y;
			x=mx[i][j-1],y=mx[i+(1<<j-1)][j-1];
			mx[i][j]=a[x]>a[y]?x:y;
		}
	}
	sum[0]=dp[0]=1;
	for(int i=1;i<=n;i++)
	{
		int x=premn[i],y=fnd(x,a[i]);
		if(y==0) dp[i]=quesm(x,i-1);
		else
		{
			int z=quemn(y+1,x);
			dp[i]=((dp[z]-quesm(y,z-1)+p)%p+quesm(x,i-1))%p;
		}
		sum[i]=(sum[i-1]+dp[i])%p;
	}
	printf("%d\n",dp[n]);
	return 0;
}