\(R_{P_j} - L_{P_j} < X_j\) であるようなクエリの答えは \(1\) なので、そうでない場合を考えます。

ある感染力に対して、相異なる任意の人の組 \((a, b)\) について、人 \(a\) から感染が始まったとき人 \(b\) も感染する、もしくは逆が成立するならば \(a, b\) 間に辺があるようなグラフを考えることができます。

このグラフ上のある辺が存在する条件は、値 \(v\) が存在して感染力 \(x\) が \(x \leq v\) を満たすことと書けます。感染力 \(x\) をだんだん下げていくような走査をしつつ、グラフの連結成分を管理することを目指します。

全ての辺を考えるかわりに以下の \(O(N)\) 本の辺のみを考えても、任意の時点で連結性が変わりません。

• 一般性を失わず \(L\) を昇順と仮定する。各 \(i \ (2 \leq i \leq N)\) について、以下の辺を考える。
  • \(\displaystyle \argmax_{1 \leq k < i} R_k = j\) とおいたときの、辺 \((i, j)\) 。

答えを求めるパートを説明します。クエリ \(j\) では、感染力 \(X_j\) におけるグラフの頂点 \(P_j\) の連結成分内の頂点 \(v\) であって \(R_v \geq L_{P_j} + X_j\) であるものの個数が答えです。連結成分を管理する際、連結成分内の \(R\) の値の多重集合も平衡二分探索木などのデータ構造で管理します。いわゆるマージテクを用いれば、計算量は \(O(N \log^2 N + Q \log N)\) です。

gcc 拡張の Policy Based Data Structures を用いるとライブラリなしでも簡潔に実装できます。実装例