概述
- 先空着。
例题
UVA1608 不无聊的序列 Non-boring sequences
-
题意：判断 \(S\) 是否 boring。所谓 boring，就是存在 \(S\) 的子串 \(s\) 满足 \(s\) 中不存在只出现一次的元素。
-
数据范围：\(n\leqslant 2\times 10^5\)。
-
注意到 \(\forall l\in (pre_i,i],r\in [i,nxt_i)\)，区间 \([l,r]\) 合法，这里 \(pre_i,nxt_i\) 表示和 \(i\) 相同的前驱/后继位置，若不存在则赋极小/极大。
-
于是考虑构建二维平面，\(l\) 为 \(x\) 轴，\(r\) 为 \(y\) 轴，对每个 \(i\)，我们将其转化为一个矩形覆盖。最后问题就是矩形面积并是否等于 \(\dfrac{n(n+1)}{2}\)。
-
显然树套树无意义也不划算，使用扫描线+差分实现，\(O(n\log n)\)。
P3246 [HNOI2016] 序列
-
题意：给定序列 \(a_{1\sim n}\)，\(Q\) 组询问，形如求子串 \([l,r]\) 的所有子串的最小值之和。形式化地，求 \(\sum\limits_{l=L}^R \sum\limits_{r=l}^R \min_{i=l}^r a_i\)。
-
数据范围：\(n,Q\leqslant 10^5\)。
-
考虑 \(l,r\) 二维平面，发现只有满足 \(x\leqslant y\) 的点 \((x,y)\) 有意义，即一个左上三角。
-
注意到 \(\forall L\leqslant l\leqslant r\leqslant R\)，\((L,R)\) 在矩形 \((1,n),(l,r)\) 中，换言之，包含子串 \((l,r)\) 的所有串恰为二维平面上 \((l,r)\) 的左上矩形。
-
考虑扫描线，并使用线段树维护，线段树上的节点维护一个 \(sum\) 表示对应 \((l,r)\) 的所有子串的最小值之和，即题目所求。
-
为了维护我们的递推性，我们只能从右向左扫或者从下向上扫。
-
首先考虑从右向左扫，注意到此时 \(l\) 每左移 \(1\)，线段树上的点 \(r\) 的 \(sum\) 要加上 \(\min_{i=l}^r a_i\)，并不相同，于是还得维护 \(mn\) 表示 \(l\sim r\) 的最小值，实质上将问题转化为 \(chkmin\) 和历史版本和，这是经典的。
-
容易发现从下向上扫和从左向右扫并没有本质区别。