問題

http://codeforces.com/contest/1042/problem/D

数列 a_n が与えられる。[l, r] の区間和が t 未満になる区間の数を求めよ。

考え方

まず、数列の連続する区間和は累積和の 2 点で求められます。

今、求めるべき区間はある 2 点 i, j (i < j) について a_j - a_i < t となるような i, j です。j を固定すると求める i は a_j - t < a_i を満たす i になります。このような i は BIT で転倒数を求める要領と同じ考え方で求めることができます。

「数列の要素を BIT の index と見立てて、区間和で個数を求めていく」という考え方です。

さて、BIT で条件を満たす i の個数を求めるとして、問題は累積和をとったときにその要素が最大で | t | <= 2 * 10¹⁴ 未満になることです。 BIT の要素とするには値が大きすぎます。

このような場合、数列の関係性を維持したまま、要素の index を小さくしたいです。これは座標圧縮を利用することができます。すると BIT の index は高々 n+1 におさまるので BIT の index として利用することができます。

さて j を固定したときに求める i は a_j - t < a_i を満たす i でした。座標圧縮すると圧縮後の index でどこから足して良いかわからなくなりますが、これは元の累積和数列を利用することで求めることができます。すなわち元の数列で a_j - t よりも大きい a_k の座標圧縮後の index から求めれば良いことがわかります。

Submission #43032467 - Codeforces