https://emtubasa.hateblo.jp/entry/2019/10/22/172441

解法

それぞれのタイミングでの、 $A_{i} - A_{i-1}$ の差がわかれば、 $S,T$ のどちらかをかけつつ総和を求めればよいです。
それぞれの差について注目すると、ある区間 $[l,r]$ が与えられたときに、 $A_{i} - A_{i-1}$ に影響が出るのは、 $(A_{l-1},A_{l}),(A_{r},A_{r+1})$ の2つのペアのみになります。これ以外の部分、およびこれ以外のタイミングで影響を及ぼすことはありません。
ので、はじめに全ての $A_{i} - A_{i-1}$ を求めておき、クエリが来るたびに、上記の2つのペアに対して $X$ を加(減)算して、その部分だけ計算しなおす、ということを繰り返せば、高速に答えを求めることができます。

感想

$N$ の与えられ方についてはじめ勘違いしていたので危なかったです…
(๑>﹏<๑｀)ぷぇーン現象