排列

https://codeforces.com/contest/1156/problem/E 题目大意 给出 $n$ 长的排列 $p$。问其中有多少 $l, r$ 子段满足 $p_l + p_r = \max_{i = l}^{r} p_i$。 $3 \le n \le 2 \times 10^5$。$1 \le p_i \le n$ 且不重复。 简要题解 因为涉及到区间最值，想到笛卡尔树。建出最大值为根的笛卡尔树之后相当 …

https://codeforces.com/contest/2056/problem/B 题目大意 给出一个 $n (n \le 1000)$ 长的未知排列和已知的 $n$ 个点的图，如果在排列中 $1 \le i < j \le n$ 且 $p_i < p_j$，则图上有一条 $<p_i, p_j>$ 的无向边。邻接矩阵的形式给出图，问排列是什么。 简要题解 直接看 $1$ 放在排列的什么位置。因 …

https://codeforces.com/contest/1913/problem/D 题目大意 给出一个 $n \ (1 \le n \le 3 \times 10^5)$ 排列 $p$。可以做如下操作任意次： 选出一个区间 $[l, r]$ 将其中除了最小元素以外的元素全部删掉。 问结果数组共有多少种。结果对 $998244353$ 取模。 简要题解 观察： 注意到 $1$ 永远删不掉。 考虑 $2$ …