邢台网站优化服务平台,网络维护一个月多少钱,滕州seo,他达拉非什么是原题链接#xff1a;D. Array Collapse 题目大意#xff1a; 给你一个长度为 n n n 的排列 p p p #xff0c;排列的定义为 [ 1 , 2 , 3 , . . , n ] [1,2,3,..,n] [1,2,3,..,n] 中每个数都出现 恰好 一次。
你可以做 任意多次 这样的操作#xff1a;
选出一个任意长度…原题链接D. Array Collapse 题目大意 给你一个长度为 n n n 的排列 p p p 排列的定义为 [ 1 , 2 , 3 , . . , n ] [1,2,3,..,n] [1,2,3,..,n] 中每个数都出现 恰好 一次。
你可以做 任意多次 这样的操作
选出一个任意长度的子数组数组中连续的一段保留其最小的元素并将其他元素从数组中删去。
现在询问你按上面的方法操作之后最终可以获得多少个互不相同的数组答案对 998 998 998 244 244 244 353 353 353 取模后输出。
解题思路 我们可以发现一个事实
因为每次都是保留一个最小元素假设我们想要保留某一个元素在最终数组里那么我们只能删除它两边比它大的元素。
假设数组为 [ 4 , 3 , 5 , 2 , 1 , 8 , 6 , 7 ] [4,3,5,2,1,8,6,7] [4,3,5,2,1,8,6,7]
则 3 3 3 只能删除 [ 1 , 3 ] [1,3] [1,3] 区间的元素 2 2 2 只能删除 [ 1 , 4 ] [1,4] [1,4] 区间的元素而最小值 1 1 1 可以把区间 [ 1 , 8 ] [1,8] [1,8] 的元素全都删完这里的删完是指的是除了自己以外的元素。
我们发现每个点都管辖着一个区间我们可以联想到 笛卡尔树 。
比如我们按照下标满足二叉搜索树权值满足小根堆的方式按照上面的数组所构建出来的笛卡尔树就是 一个节点的子树就是他能管辖到的位置。
这样我们就能对每个节点管辖到的左右子树进行分类讨论了。
对管辖了 [ 1 , n ] [1,n] [1,n] 的根结点 1 1 1 无论如何也不能删去没有贡献。一个节点 u u u 而言如果我们要保留它显然它的左右子树的方案是独立的因此保留它的方案数有 a n s l × a n s r ansl \times ansr ansl×ansr 种。假设不保留它而且它管辖了 [ 1 , x ] [1,x] [1,x] 的一段区间说明它是其左边的最小值比如 3 3 3 。我们左边没有比我们更小的数来删掉节点 u u u 了因此我们只能被右边比我们小的 2 2 2 删去右子树会被随之吞并而左子树是独立的所以方案数有 a n s l ansl ansl 种。假设不保留它而且它管辖了 [ x , n ] [x,n] [x,n] 的一段区间说明它是其右边的最小值比如 6 6 6 。我们右边没有比我们更小的数来删掉节点 u u u 了因此我们只能被左边比我们小 1 1 1 的删去左子树会被随之吞并而右子树是独立的所以方案数有 a n s r ansr ansr 种。假设不保留它而且它管辖了 [ x , y ] [x,y] [x,y] 的一段区间说明它左右都有比他小的值 。我们既可以被左节点删除又可以被右节点删除所以方案数有 a n s l a n s r − 1 anslansr-1 anslansr−1 种。首先左右子树是独立的我们点 u u u 被左边删了而右子树有一个全删完的方案此时我们计算了一个删空点 u u u 整个子树的方案。而我们被右边删了左子树有一个全删完的方案此时我们又计算了一次删空点 u u u 的方案点 u u u 的子树空被计算了两次所以要减去 1 1 1
我们只需要从 1 1 1 开始然后跑递归处理每个点作为子树的方案值回溯过程中 D P DP DP 即可。
时间复杂度 O ( n ) O(n) O(n)
AC代码
#include bits/stdc.h
using namespace std;using PII pairint, int;
using i64 long long;templateclass Ty
struct CartesianTree {vectorint stk;vectorint L, R;CartesianTree() {}tupleint, vectorint, vectorint work(const vectorTy A) {L.assign(A.size(), 0), R.assign(A.size(), 0);int n A.size() - 1;for (int i 1; i n; i) {int lst 0;while (stk.size() A[stk.back()] A[i]) {lst stk.back();stk.pop_back();}if (stk.size()) {R[stk.back()] i;}if (lst) {L[i] lst;}stk.emplace_back(i);}return {stk[0], L, R};}
};const int mod 998244353;void solve() {int n;cin n;vectorint arr(n 1);for (int i 1; i n; i) {cin arr[i];}CartesianTreeint T;auto [root, L, R] T.work(arr);auto DFS [](auto self, int u, int l, int r) - i64 {i64 ansl 1, ansr 1;if (L[u]) ansl self(self, L[u], l, u - 1);//有左子树就去左子树if (R[u]) ansr self(self, R[u], u 1, r);//有右子树就去右子树i64 ans ansl * ansr % mod;//保留根的答案//删除根的答案if (l 1 r n);//跳过根节点else if (l 1) {//只能被右边删ans ansl;} else if (r n) {//只能被左边删ans ansr;} else {//左右都能删ans ansl;ans ansr;ans - 1;}return (ans mod) % mod;};cout DFS(DFS, root, 1, n) \n;
}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t 1; cin t;while (t--) solve();return 0;
}
