ABC346-G Alone の解法です．典型だったのか．知らなかった….
問題へのリンク
問題概要
$A = (A_1, \dots, A_N)$ が与えられる． $1 \leq L \leq R \leq N$ で，$A_L, A_{L + 1}, \dots, A_R$ の中に1度だけ出現する数がある ような $(L, R)$ の組の数を答えよ．
制約: $N \leq 2\times 10^5$, $1 \leq A_i \leq N$
前提知識
辺が座標軸と平行な長方形 $N$ 個の頂点の座標が与えられた時， 被覆する図形の面積は，次の方法で $O(N \log N)$ で求められる．
適宜座標圧縮する．頂点のx座標の小さい順にソートして平面走査する．ベクトル $S$ を用意する．
- 左端頂点 $(x, y_1)$, $(x, y_2)$ が現れたら，$S[y_1], …, S[y_2 - 1]$ に$1$を加える．
- 右端頂点 $(x, y_3)$, $(x, y_4)$ が現れたら，$S[y_3], …, S[y_4 - 1]$ に$-1$を加える．
- $S[\min], … S[\max]$ のうち，$0$ であるものの数を $t$ として，$\max - \min + 1 - t$ を答に加える．
愚直だと $\Omega(N^2)$ かかるが，次の lazy segment tree を使うと $O(N \log N)$ になる．
- モノイド集合の要素は，区間の最小値と最小値を与える点の数．
- 作用は，定数を加えること．
こうすると，「値が $0$ であるものの数」は，「最小値が $0$ であるとき，最小値を与える点の数，そうでない時 $0$」 と言い換えられる．
解法
各 $m$ に対して， $A_i = m$ となる $i$ を列挙して $i_1, \ldots, i_K$ とし，適当に番兵を置けば， グリッド内の長方形 $\{ (x, y) \mid i_k < x \leq i_{k + 1},\; i_{k + 1} \leq y < i_{k + 2} \}$ たちで被覆される部分が，題意を満たす．