P10833 [COTS 2023] 下 Niz
题目大意详细题目传送门
给出 \(n\) 和 \(a_1\cdots a_n\)，求有多少个区间 \(\) 满足 \(a_l\cdots a_r\) 是 \(1\) 到 \(r-l+1\) 的排列。
\(a_i\leq n\leq10^6\)
思路
对于 \(\)，要满足
[*]\(\max_{i=l}^r a_i=r-l+1\)
[*]\(\forall i,j,a_i\neq a_j\)
可以猜到真正符合条件的区间应该不会很多，又因为区间一定要有且仅有一个 \(1\)，所以可以和 \(1\) 的位置考虑。先考虑一个位置 \(i\) 作为区间端点的情况，所以维护对于一个位置 \(i\) 上一个 \(1\) 和下一个 的位置 \(p_i,n_i\)。发现只考虑 \((i,i+\max_{j=i}^{n_i}a_j-1)\) 和 \((i-\max_{j=p_i}^i a_j+1,i)\) 即可。首先这个肯定是对的，但是为什么不会少呢？是因为对于再前面或后面的，如果还有最大值会被前面的左端点也算上，所以不会算漏只会算重。所以现在有不超过 \(2n\) 个区间需要判断第 \(2\) 个条件。
对于这一个条件，一般做数据结构题做多了就会想到就是求 \(\mathrm{mex}(a_l\cdots a_r)\overset{?}{=} r-l+2\)。
区间 \(\mathrm{mex}\) 是不好求的，但是考虑到我们只有 \(2n\) 个区间，所以考虑离线后排序。前缀 \(\mathrm{mex}\) 相对好求，现在考虑如果把 \(a_l\) 删去带来的影响。发现就是可以在下一个 \(a_l\) 之前使用。所以也就是对于 \(m_i\) 表示 \(\mathrm{mex}\in\)。我们可以找到 \(f_i\) 表示下一个 \(a_i\) 的位置。于是对于每一次 \(a_l\) 的删除操作，我们可以将 \(m_i\leftarrow \min(m_i,a_l),i\in\)。对于一个 \(\) 判断 \(m_r\overset{?}{=}r-l+2\) 即可。
时间复杂度 \(O(n\log n)\)。
代码
#include#define rep(i,a,b) for(ll i=(a);i
页:
[1]