JOI春合宿2019-Day1-1 Examination（問題はこちら,ジャッジはこちら,解説はこちら）の解説です。
解法メモです。
問題概要
$N$ 人の学生がいて、それぞれ数学と情報で $S_i,T_i$ の点数を取った。
$Q$ 回のクエリが与えられるので、$S_i\geq X_j,T_i\geq Y_j,S_i+T_i\geq Z_j$ を満たす $i$ の個数を、それぞれの $j$ について求めよ。
考察
- 制約がでかい、やばそう
- とりあえず $X_j+Y_j\geq Z_j$ のときは、$Z_j$ の条件は実質気にしなくていいので、クエリとデータを $X_j,S_i$ 順にソートして自動的に $X_j$ の条件を満たすようにしておき、$Y_j$ 以上の $T_i$ をもつ $i$ の個数を求める $\rightarrow$ BITなりセグ木なりでできる
- 問題は $X_j+Y_j<Z_j$ のとき、この時は $X_j,Y_j,Z_j$ 全部気にしないといけない、一個ソートしておいて無視したにしても他の $2$ つに条件が絡まる
- これを処理できるデータ構造を知っていますか？僕は知りません（後から見たネット上の解説によるとうまく座圧するとできるらしいが、めんどくさそう、やりたくない、やめたい、やめてしまった）
- 知らないので、不等式処理でなんとかしようとするが、できない（それはそう、ここで3時間ほど溶かす、睡眠時間はドブへ）
- 音楽の授業中に頑張って考察をすると、後者のクエリをさらに二つに分割できないか？となる
- $X_j\leq S_i<Z_j-Y_j$ と、$Z_j-Y_j\leq S_i$ に分けてみると、前者では $Z_j\leq S_i+T_i$, 後者では $Y_j\leq T_i$ が題意と必要十分であることに気づく
- これなら、$X_j$ に関する条件は自動的に満たすようにしておき、あとは $Y_j$ と $Z_j$ をそれぞれ別々に気にするだけでいい $\rightarrow$ 完全勝利
- まとめると、次のようになる
- 基本的にクエリとデータは $X_j,S_i$ の順にソートしておき、残りの条件だけ気にすればいい、という状態にする
- $X_j+Y_j\geq Z_j$ のときは、$Y_j$ と $T_i$ の大小関係だけ見ればいいので、BITかセグ木で殴れる
- そうでない時は、$X_j\leq S_i<Z_j-Y_j$ の範囲だけに対しては $Z_j\leq S_i+T_i$ を満たすか見る、$Z_j-Y_j\leq S_i$ については $Y_j\leq T_i$ を満たすか見る
- これで気にすべきパラメータを絞れたので高々 $Y_j$ 用と $Z_j$ 用、2本のセグ木で処理できる（使いまわせば1本でも済む）
- セグ木に対する取得のタイミングとかが一個一個のクエリからいい感じには定まらないし、そもそも異なるタイミングで複数の取得が必要な場合もある（たとえば $S_i$ を区間で挟むなら2回取得して引き算する必要がある）ので、セグ木に対して必要な取得操作をまとめておいてソートすると吉
以上でした。これで強そうなデータ構造を使わずに、セグ木1本でこの問題が解けました。
SegmentTree on SegmentTreeとかいらないでしょ？（威圧）
ところでガストのチーズinハンバーグって、名前的にハンバーグは脇役でチーズが主役ですよね。（どうでもいい）
実装
これを見てください。
結構コードが汚くてごめんなさい。
おわりに
データ構造の知識がないとこういう変な考察で変な解き方をすることになります。
勉強はちゃんとしましょう。
ねむいですね。おやすみなさい。