まず、\(1\) 以上 \(N\) 以下の整数 \(i\) を固定し、\(A_L, A_{L + 1}, \ldots, A_R\) の中に \(A_i\) が \(1\) 度だけ出現するような \(1 \leq L \leq R \leq N\) を満たす \((L, R)\) の組はどのようなものか考えます。すると、以下の結論が従います。

• \(A_j = A_i\) かつ \(j < i\) を満たす最大の整数 \(j\) を取る。ただし、そのような \(j\) が存在しない場合は、\(j = 0\) とする。

• \(A_i = A_k\) かつ \(i < k\) を満たす最小の整数 \(k\) を取る。ただし、そのような \(k\) が存在しない場合は、\(k = N + 1\) とする。

• \(j < L \leq i\) かつ \(i \leq R < k\) を満たす整数の組 \((L,R)\) が条件を満たすものである。

すると、問題の条件を満たす組 \((L,R)\) 全体は上で求めた組の \(i = 1,2, \ldots, N\) の和集合であるため、以下の問題が解ければよいことがわかります。

整数の組 \((x_i,y_i,z_i,w_i)\) が \(N\) 個与えられる。ある \(i\) に対して \(x_i \leq L \leq y_i\) かつ \(z_i \leq R \leq w_i\) を満たす整数の組 \((L, R)\) の組の個数を求めよ。

上の考察から与えられる組は必ず \(y_i = z_i\) を満たしていますが、その性質を利用せずとも今後の議論ができるため言い換え後の問題ではそのような条件を課していないことに注意してください。

上で与えられた問題を以下のように言い換えることで見通しがよくなります。

\(0\) で初期化された \(2\) 次元配列 \(B\) がある。整数の組 \((x_i, y_i, z_i, w_i)\) が \(N\) 個与えられ、各 \(i\) に対して以下の操作を行う。

• \(x_i \leq l \leq y_i\) かつ \(z_i \leq r \leq w_i\) を満たすすべての整数の組 \((l,r)\) について \(B_{l,r}\) に \(1\) を加算する。

\(B\) の要素であって、値が正であるものの個数を求めよ。

この問題は平面走査をすることでさらに以下のように言い換えることができます。

\(0\) で初期化された長さ \(N\) の数列 \(C\) が与えられる。また、答えの値を \(0\) で初期化する。整数の組 \((x_j, y_j, z_j, w_j)\) が \(N\) 個与えられ、\(i = 1,2,\ldots, N\) の順で以下の操作を行う。

• \(x_j = i\) を満たす整数の組 \((x_j, y_j, z_j, w_j)\) に対して \(C_{z_j}, C_{z_j + 1}, \ldots, C_{w_j}\) に \(1\) を加算する。

• \(C\) の要素であって、値が正であるものの個数を求め、答えに足し合わせる。

• \(y_j = i\) を満たす整数の組 \((x_j, y_j, z_j, w_j)\) に対して \(C_{z_j}, C_{z_j + 1}, \ldots, C_{w_j}\) に \(-1\) を加算する。

この操作は愚直に行うと時間計算量 \(\Theta(N^2)\) ですが、lazy segment tree を用いることにより \(O(N \log N)\) へと高速化できます。

具体的には、区間の最小値および最小値の個数を持ち、区間加算を行うことでこの問題を解くことができます。

操作の過程で \(C\) の要素はすべて非負であるため \(C\) の要素であって \(0\) であるものの個数が求まればよいこと、また \(C\) の要素において \(0\) が存在するならば \(C\) の最小値は \(0\) であることを利用していることに注意してください。

補足 : このような長方形の和集合の面積を求める問題は典型的な有名問題です（参考 : Library Checker）。