Educational Codeforces Round 22 E - Army Creation
バチャをしました
問題文
人の兵士がいて、
番目の兵士のタイプは
です。
Vova はこのなかからできるだけ多くの兵士をを雇って軍隊を作りたいです。
ただし、同じタイプの兵士は 人までしか雇えません。
各クエリについて、 の兵士から軍隊を作るときの軍隊の人数を求めてください。
ただし、クエリ暗号化がされていて、オンラインで答える必要があります。
考察
だと種類数になって、
が変わっても同じように解けそう。
区間 種類数 競プロ [検索🔎]
hama-du-competitive.hatenablog.com
オンラインで答える方法が書いてある
同じ数をちょうど2つ含む区間 → 同じ数をちょうど 個含む区間 とすればよい
区間を (始点, 終点) の2次元平面上の点に落とし込んで、 [典型]
に含まれる区間の数
を領域木で求める。
