给定序列 \(a_1,\dots,a_n(n \le 5 \times 10^5, 3s)\) ，\(m\) 次询问，每次询问给出 \(l,r\) ，问有多少组 \((i,j,k)\) 满足 \(l\le i<j<k\le r,\;a_i=a_k>a_j\) 。
这个题看起来如果离线下来按 \(r\) 排序做不太能 \(\log\) 做，考虑一下根号做法：莫队！
既然考虑了莫队，先看看在末尾加一个元素 \(a_x\)，贡献：
\[\begin{aligned} &= \sum\limits_{y} [a_x == a_y] \sum\limits_{i = y}^x [a_i < a_x] \\ &= \sum\limits_{y} [a_x == a_y] (\sum\limits_{i = 1}^x [a_i < a_x] -\sum\limits_{i = 1}^y [a_i < a_y]) \end{aligned}
\]
用树状数组可以轻松算出 \(c_x = \sum\limits_{i = 1}^x [a_i < a_x]\)。贡献化简为 \(\sum\limits_{y} [a_x == a_y](c_x - c_y)\)，即 \(c_x\sum\limits_{y} [a_x = = a_y] - \sum\limits_{y} [a_x == a_y] c_y\) 。转化为这个形式就有手就行了。删除一样的。
时间复杂度：\(O(m \sqrt m)\)。
这题主要想到莫队就差不多了。