2019-10-22 第16回JOI本戦 A - フェーン現象 (Foehn Phenomena) 未分類 問題 提出コード 解法 それぞれのタイミングでの、の差がわかれば、のどちらかをかけつつ総和を求めればよいです。 それぞれの差について注目すると、ある区間が与えられたときに、に影響が出るのは、の2つのペアのみになります。これ以外の部分、およびこれ以外のタイミングで影響を及ぼすことはありません。 ので、はじめに全てのを求めておき、クエリが来るたびに、上記の2つのペアに対してを加(減)算して、その部分だけ計算しなおす、ということを繰り返せば、高速に答えを求めることができます。 感想 の与えられ方についてはじめ勘違いしていたので危なかったです… (๑>﹏<๑`)ぷぇーン現象