(WIP)

本問題は、永続セグメント木を用いて解くこともできます。

まず、\(L=1\) としてよいです。この時の答えを \(f(R,X)\) とすると、与えられた \(L,R,X\) に対する答えは \(f(R,X)-f(L-1,X)\) と表せるためです。

与えられた \(A\) を座標圧縮します。そして、\(A\) の要素を \(i\) の昇順に見ていくと、オフラインであれば1点変更と区間和の取得ができる何らかのデータ構造に足し引きすれば求めたい値を取得できます。

しかし、ここでクエリがオンラインであることが重大な障壁となります。これを解決する方法は、過去のデータにアクセスできる、永続セグメント木などのデータ構造を使うことです。