典型力。ダブったペアのぶん種類数が減る。 ダブったペアの数え上げにfenwicktreeを使う。atcoder.jpfenwicktreeにどう情報を入れるか、数え上げをどう実現するかがミソでしょうか。

数値とかのソートされた配列aに対して lower_bound(a.begin(), a.end(), k) は aの中で ai≧k となる最小のポインタを求める。 upper_bound(a.begin(), a.end(), k) は aの中で ai>k となる最小のポインタを求める。 これらを使ってaの中の値がkの要素の数は …

優先度付きキュー priority_que 優先度の高いものへのアクセスが早い priority_que<int> p; p.push(1); // 1を追加 p.top(); //１番大きい要素を返す p.pop(); //１番大きい要素をpop コンストラクタ＋push_back emplace_back 型の違うvectorとかに入れるときに楽</int>…