题解：AT_arc115_e [ARC115E] LEQ and NEQ

来点不用容斥的不一样的做法。

考虑 $a_i$ 值较小的那些对其他位置的影响是简单的，必定会减少恰好 $1$ 种可能情况。

所以我们考虑先确定 $a$ 值较小的位置，这启发我们用笛卡尔树。

我们建立小根笛卡尔树。

考虑对于笛卡尔树的一个子树，设其代表的区间为 $[l,r]$，分割点为 $p$。（这里我们只讨论 $1<l\le r<n,l<p<r$ 的情况，其他情况是简单的）

发现这个区间两边填多少其实不重要，重要的是两边填的东西是否相等。

于是，我们记 $f_{l,r,0/1}$ 表示区间两边填的数是否相等，该区间内的填数方法数。

如果两边不相等：
- 如果分割点和两边都不相等，有 $a_p-2$ 种选法。
$$f_{l,r,0}\gets f_{l,p-1,0}\times f_{p+1,r,0}\times (a_p-2)$$
- 如果分割点和某一边相等，那么只有 $1$ 种方法。
$$f_{l,r,0}\gets f_{l,p-1,1}\times f_{p+1,r,0}$$
$$f_{l,r,0}\gets f_{l,p-1,0}\times f_{p+1,r,1}$$

如果两边相等：
- 如果分割点和两边都不相等，有 $a_p-1$ 种选法。
$$f_{l,r,1}\gets f_{l,p-1,0}\times f_{p+1,r,0}\times (a_p-1)$$
- 如果分割点和某一边相等，那么只有 $1$ 种方法。
$$f_{l,r,1}\gets f_{l,p-1,1}\times f_{p+1,r,1}$$

总复杂度 $O(n)$。

代码如下（使用的是 ST 表建笛卡尔树）。

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1000005,mod=998244353;
int n,a[N];
int Log2[N],st[N][20];
void getst()
{
	Log2[1]=0;
	for(int i=2;i<=n;i++) Log2[i]=Log2[i/2]+1;
	for(int i=1;i<=n;i++) st[i][0]=i;
	for(int j=1;j<=Log2[n];j++)
		for(int i=1;i<=n;i++) st[i][j]=a[st[i][j-1]]<a[st[i+(1<<j-1)][j-1]]?st[i][j-1]:st[i+(1<<j-1)][j-1];
}
int find(int l,int r)
{
	int k=Log2[r-l+1];
	return (a[st[l][k]]<a[st[r-(1<<k)+1][k]])?st[l][k]:st[r-(1<<k)+1][k];
}
int idx;
int f[N][2],ls[N],rs[N];
void work(int l,int r,int x)
{
	if(l==r)
	{
		if(l==1||r==n) f[x][0]=a[l]-1;
		else f[x][0]=a[l]-2,f[x][1]=a[l]-1;
		return;
	}
	int p=find(l,r);
	if(l<p) ls[x]=++idx,work(l,p-1,idx);
	if(p<r) rs[x]=++idx,work(p+1,r,idx);
	if(l==1&&r==n)
	{
		if(p==l) f[x][0]=(long long)f[rs[x]][0]*a[p]%mod;
		else if(p==r) f[x][0]=(long long)f[ls[x]][0]*a[p]%mod;
		else f[x][0]=(long long)f[ls[x]][0]*f[rs[x]][0]%mod*a[p]%mod;
	}
	else if(l==1)
	{
		if(p==l) f[x][0]=((long long)f[rs[x]][0]*(a[p]-1)+(long long)f[rs[x]][1])%mod;
		else if(p==r) f[x][0]=(long long)f[ls[x]][0]*(a[p]-1)%mod;
		else f[x][0]=((long long)f[ls[x]][0]*f[rs[x]][0]%mod*(a[p]-1)+(long long)f[ls[x]][0]*f[rs[x]][1])%mod;
	}
	else if(r==n)
	{
		if(p==l) f[x][0]=(long long)f[rs[x]][0]*(a[p]-1)%mod;
		else if(p==r) f[x][0]=((long long)f[ls[x]][0]*(a[p]-1)+(long long)f[ls[x]][1])%mod;
		else f[x][0]=((long long)f[ls[x]][0]*f[rs[x]][0]%mod*(a[p]-1)+(long long)f[ls[x]][1]*f[rs[x]][0])%mod;
	}
	else
	{
		if(p==l)
		{
			f[x][0]=((long long)f[rs[x]][0]*(a[p]-2)+(long long)f[rs[x]][1])%mod;
			f[x][1]=(long long)f[rs[x]][0]*(a[p]-1)%mod;
		}
		else if(p==r)
		{
			f[x][0]=((long long)f[ls[x]][0]*(a[p]-2)+(long long)f[ls[x]][1])%mod;
			f[x][1]=(long long)f[ls[x]][0]*(a[p]-1)%mod;
		}
		else
		{
			f[x][0]=((long long)f[ls[x]][0]*f[rs[x]][0]%mod*(a[p]-2)+(long long)f[ls[x]][1]*f[rs[x]][0]+(long long)f[ls[x]][0]*f[rs[x]][1])%mod;
			f[x][1]=((long long)f[ls[x]][0]*f[rs[x]][0]%mod*(a[p]-1)+(long long)f[ls[x]][1]*f[rs[x]][1])%mod;
		}
	}
//	printf("%d %d:%d %d\n",l,r,f[x][0],f[x][1]);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	getst();
	idx=1;
	work(1,n,1);
	printf("%d\n",f[1][0]);
}
```

正在渲染内容...