LGP4229题解

某位寄吧的故事

下文的 \(m\) 即为题面中的 \(Q\)。

离散化，把序列变成 \(O(2m)\) 个部分，然后对这 \(O(2m)\) 个部分把最大值求出来，每次把最大值相同的部分拉出来，再把限制和这个最大值相同的也拉出来。我们假装这个最值叫 \(c\)。

然后是 \(dp\)。\(dp[n][k]\) 表示推到第 \(n\) 段，上一个最大值在第 \(k\) 段时的合法方案数量。

注意到如果两个区间有包含关系，那么大的那个区间相当于不存在。

设 \(L[n]\) 表示右端点在第 \(n\) 段的区间中，左端点最靠右的那个左端点。如果没有那就是 \(0\)。没说就是零卡

然后设 \((l[n],r[n]]\) 为第 \(n\) 段区间在原序列上的左右端点。

不难发现这题其实是 P5204 的加强版（雾）

\[dp[n][k]=[L[n]\leq k]dp[n-1][k]\times(c-1)^{r[n]-l[n]} \]

\[dp[n][n]=\sum_{i=1}^{n-1}dp[n-1][i]\times(c^{r[n]-l[n]}-(c-1)^{r[n]-l[n]}) \]

游戏结束。

复杂度 \(O(m\log n)\)。

#include
#include
#include
#include
typedef unsigned ui;
const ui M=505,mod=998244353;
ui n,m,A,s,k[M],V[M],tl[M],tr[M],l[M<<1],r[M<<1];ui len,lsh[M<<1];
std::vectorc[M],q[M];
inline ui max(const ui&a,const ui&b){
	return a>b?a:b;
}
inline ui min(const ui&a,const ui&b){
	return a>b?b:a;
}
inline ui pow(ui a,ui b){
	ui ans(1);for(;b;b>>=1,a=1ull*a*a%mod)if(b&1)ans=1ull*ans*a%mod;return ans;
}
inline ui Solve(const ui&k){
	static ui L[M<<1],dp[M<<1],tag[M<<1];
	const ui&v=V[k],&len=c[k].size();
	for(ui i=0;i>=1,r>>=1){
			if(~l&1)mx[l^1]=min(mx[l^1],V);
			if(r&1)mx[r^1]=min(mx[r^1],V);
		}
	}
	inline void pushdown(){
		for(ui u=1;u().swap(c[i]),std::vector().swap(q[i]);
		printf("%u\n",ans);
	}
}