joisc2008 台風 (Typhoon) （難易度9）
難しい
注意
セグメント木とかは半開区間で扱います
座標圧縮の計算量を無視しています（サイズが$ nのとき、圧縮にかかる計算量は$ O(n)、元の座標から圧縮された座標を求めるものの計算量は$ O(\log n)になるはず）
解説
小課題 1 は愚直に実装、小課題 2 は座標圧縮をして累積和を実装すると通る。
ここからは満点の解説をする（座標圧縮をしたことを前提にし、$ a,b + 1,pを全て座標圧縮したときのサイズを$ sizeとおく。このとき$ sizeは高々$ 2N + Q）。
まず 1 つのクエリ$ (p, q, r)に着目して解いてみる。
$ i 個目までの台風のうち、地点$ p を通過したものの個数を$ count[i][p] とおく。すると、このクエリの答えは$ count[r][p] - count[q - 1][p] となる。なので、$ count[r][p], count[q - 1][p] を求めればいい。
これを$ m個のクエリそれぞれに対して求める。
双対セグメント木や遅延セグメント木を使い、台風の番号が小さい順に加算していくと、$ i が小さい順に、任意の$ j\ (1 \leq j \leq size) に対して、$ count[i][j] が$ O(\log size) で求まる。
よって、クエリに必要なもの（上のもの）だけ求めると計算量が$ O(m\log size)となり、TL に間に合う。
実装では、最初にクエリを$ q の昇順にソートして、$ count[q - 1][p] を全て求めてから、クエリを$ r の昇順にソートして、$ count[r][p] を全て求めている。
他にも、台風を平方分割をしてそれぞれの累積和を求めてから、各クエリ$ O(\sqrt{n})で求める方法もある（これだとオンラインクエリでも対応できるが、TL と ML が少々厳しい）。