- https://codeforces.com/contest/643
- https://codeforces.com/contest/674 (div1)
- https://codeforces.com/contest/673 (div2)
A. Bear and Colors
全部の区間の答を計算します．$L$ を固定して $R$ をインクリメントしていきます．各色の出現回数と現時点での答を持っておけばよいです．
B. Bear and Two Paths
$a,b,c,d$ がすべて異なるとすると，$N=4$ なら不可能，そうでないなら，$a,c,…,d,b$ と $c,a,…,b,d$ で間に残りの点を挟めば最小本数で目的達成です．
一致がある場合も適切に場合分けします．
C. Levels and Regions
愚直な dp を書けば，cht で高速化可能だと分かります．
D. Bearish Fanpages
シミュレーションです．各頂点に対しては，TO[v] からの収入を除く収入を記録しておきます．また，親にいくらずつ配ることになっているかも記録しておきます．これらはクエリあたり $O(1)$ 時間で更新可能ですし，2 番目のクエリには答えられるようになっています．
3 番目の頂点に答えるには，ある頂点において，親の収入の多重集合を管理します．この集合に対しては要素の追加・削除と，自身から配ることになっている値の変更（全体への定数加算）しか必要ありません．よって，頂点ごとにこの min, max が取得できている状態を維持できます．あとはこれをセグメント木などにのせれば，大域的な min, max が取得できるようになります．
E. Bear and Destroying Subtrees
高さが大きくなる確率はとても小さいため，高さが小さいときのみ計算すればよい．というのが概要です．
深さ $d$ の頂点ひとつが生き残る確率は $2^{-d}$ です．union bound で，深さ $d$ 以上の頂点がひとつ以上生き残る確率は $N\cdot 2^{-d}$ 以下です．$d=D,D+1,D+2,\ldots$ に対してこの和をとったものが無視できる程度の $D$ をとって，深さ $D$ までの頂点だけを考慮します．
求値クエリは適当な木dpでできます．変更クエリごとに木dpすべての計算をやり直すことは出来ませんが，$v$ から $D$ 個分程度の祖先のところだけ再計算すればよくて，それはできます．
F. Bears and Juice
dp[日数][行動不能人数] = (max barrets) という dp を考えます．
dp[d+1][m] の計算を考えましょう．
ひとつのものを $\min(n-1,p-m)$ 人より多くが選ぶことは出来ません．
$0\leq k\leq \min(n-1,p-m)$ として，$k$ 元集合をひとつ固定するとき，ちょうどそのメンバーが選んだものの個数としてありうる最大値は，dp[d][m+k] となります．すべての部分集合でこの最大値を実現するような戦略をとることが最適な戦略となります．
dp は行列 $A$ で書けて，適当なベクトル $x$ について $A^nx$ のある成分を求めるという問題になります．あとはすべてを $\pmod{2^{32}}$ の設定で高速に計算する必要があります．素数 mod ならば Berlekamp Massey や characteristic polynomial を召喚して終わると思うのですが，今回は難しい気がします．
$n$ が連番であることは使いませんでした．baby step, giant step を考えます．適当な $K$ をとり，$A^{aK+b}x=A^b\cdot A^{aK}x$ とします．$A^0,\ldots,A^K$ を計算し，それを利用して，$A^{iK}x$ を計算しておけばよいです．
$Q\leq KL$ となる $K, L$ をとったとき，前計算では行列積を $K$ 回，行列ベクトル積を $L$ 回ということになるので，$K=\sqrt{Q/p}$ 程度が適切となると思います．クエリは行列ベクトル積の特定の成分なので $O(p)$ 時間です．
G. Choosing Ads
Boyer-Moore majority vote algorithm の変種です．
$n$ 種類以下の頻度を持ちます．何かを追加して $n+1$ 種類になったら，ひとつずつ消去します．すると最終的には，列に対して，「$n+1$ 個の distinct なものをひとつずつ削除する」ことを繰り返した結果の $n$ 種類以下のものが残っています．ここに，全体に占める割合が $1/(n+1)$ より真に大きいものは必ず残っています．
操作は列の好きなところからやってよいためこれはセグメント木で扱えて，区間代入もあわせて遅延セグメント木で解くことができます．
