早稲田大学プログラミングコンテスト2019 D - Choose Your Characters

解法

条件を満たしている区間はさらに伸ばしても必ず条件を満たすので、しゃくとり法が使えます。上手くしゃくとり法ができるように工夫をしましょう。

しゃくとり法では自キャラのほうを区間に入れたり出したりするので、それに応じて相手キャラごとに管理した値を操作するほうがやりやすいです。具体的には相手キャラ $j$ それぞれについて、

$n\lbrack j \rbrack =$ 今見ている区間 $\lbrack L, R\rbrack$ 内の自キャラ $i$ のうち、「 $i$ は $j$ に対して不利である」ような $i$ の個数

を管理すると上手くいきます。

その理由として、問題には「任意の相手キャラに対して五分または有利な自キャラが1体以上存在する」という条件が書いてありますが、入力 $N$ が大きいときにはほとんどが五分の関係なので数が非常に多いです。そのため逆に「自キャラが相手キャラに対して不利である」という関係を使うようにすると条件数が少なくて扱いやすくなります。

ここで「相手と同じキャラは自キャラとして選べる候補から除外する」という条件が厄介ですが、「自キャラ $i$ は相手の同キャラ $i$ に対して不利である」という関係を追加することでこの条件を処理することが出来ます。

区間 $\lbrack L, R\rbrack$ を選んだ時に問題の条件を満たすためには、すべての相手キャラ $j$ について「 $j$ に対して不利でない自キャラが存在する」こと、つまり $n\lbrack j \rbrack$ の最大値が区間 $\lbrack L, R\rbrack$ の長さ $R-L+1$ よりも小さいことが必要十分です。 $\max$ を取りたいので $n\lbrack j \rbrack$ の値をセグメント木で管理しましょう。

区間に自キャラ $i$ を出し入れする際には、「自キャラ $i$ が不利であるような相手 $j$ 」を事前に列挙しておいて、そのような $j$ について $n\lbrack j \rbrack$ を増減させます。不利であるという関係が全部で $N+M$ 個しかないので、この増減操作は問題全体で $O(N+M)$ 回しか行われません。