标签 单调栈 下的文章

「Codeforces 1156E」Special Segments of Permutation

题目链接：Codeforces 1156E

你有一个长度为 $n$ 的排列 $p$，假如 $p_l + p_r = \max_{i = l} ^ r p_i$，那么我们称子段 $p[l, r]$ 是特殊的。请你找出特殊的子段数量。

数据范围：$3 \le n \le 2 \times 10 ^ 5$。

「GXOI / GZOI 2019」与或和

题目链接：LOJ 3083

Freda 学习了位运算和矩阵以后，决定对这种简洁而优美的运算，以及蕴含深邃空间的结构进行更加深入的研究。

对于一个由非负整数构成的矩阵，她定义矩阵的 $\text{AND}​$ 值为矩阵中所有数二进制 $\texttt{AND(&)}​$ 的运算结果；定义矩阵的 $\texttt{OR}​$ 值为矩阵中所有数二进制 $\texttt{OR(|)}​$ 的运算结果。

给定一个 $n \times n$ 的矩阵，她希望求出：

1. 该矩阵的所有子矩阵的 $\texttt{AND}​$ 值之和（所有子矩阵 $\texttt{AND}​$ 值相加的结果）。
2. 该矩阵的所有子矩阵的 $\texttt{OR}​$ 值之和（所有子矩阵 $\texttt{OR}​$ 值相加的结果）。

接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题，所以这个问题就交给你了。

由于答案可能非常的大，你只需要输出答案对 $10 ^ 9 + 7​$ 取模后的结果。

数据范围：$1 \le n \le 10 ^ 3$，$\text{矩阵中的自然数} \le 2 ^ {31} - 1$。

「POJ 3415」Common Substrings

题目链接：POJ 3415

字符串 $T$ 的子串定义为：

$$ T(i,k) = T_iT_{i + 1}\cdots T_{t + k - 1}, 1 \le i \le i + k - 1 \le \lvert T \rvert $$

给定两个字符串 $A, B$ 和一个整数 $K$，我们定义 $S$ 为三元组 $(i, j, k)$ 集合：

$$ S = \{(i, j, k) \mid k \ge K, A(i, k) = B(j, k)\} $$

你需要求出集合 $S$ 的大小 $\lvert S \rvert$。

数据范围：$1 \le \lvert A \rvert, \lvert B \rvert \le 10 ^ 5$，$1 \le K \le \min(\lvert A \rvert, \lvert B \rvert)$。

「AHOI 2013」差异

题目链接：LOJ 2377

给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀，求：

$$ \sum_{1 \le i < j \le n} \text{len}(T_i) + \text{len}(T_j) - 2 \times \text{lcp}(T_i, T_j) $$

其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a, b)$ 表示字符串 $a$ 和字符串 $b​$ 的最长公共前缀。

数据范围：$2 \le n \le 5 \times 10 ^ 5$。