【paiza解いてみた】村人の友好関係 (paizaランク S 相当)

# はじめに
こんにちは。[paiza×Qiitaコラボキャンペーン](https://paiza.jp/pages/campaign/paiza-qiita)で、記事を投稿すると賞が当たるというのをやっているので、参加して問題を解いてみました。

今回解いたのは「[村人の友好関係](https://paiza.jp/works/mondai/s_rank_skillcheck_archive/group_popularity)」。
Sランクなだけあり、正解率は62.7%と低めです。

<details open>
<summary>以下ネタバレ注意です。（クリックで余白を折りたたみ）</summary>

- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
- - -
</details>

# 解いた感想
高度なデータ構造を使う必要があり、Sランクの中でも相当難しかったです。
問題を解くためにデータ構造を書いてしまったため、せっかくなのでここに供養しておきます。

# 解法
時間計算量は$O(M+QN\log M)$です。

手順:
1. 隣接リスト形式のグラフを構築
2. 最大値を保持する多重集合データ構造を用意（グループの内外にまたがる友好関係の友好度を入れる）
3. クエリで与えられた頂点に隣接する友好関係すべてに対し、多重集合に含まれるかを再計算

プログラミングを愛する方なら言葉など蛇足でしょう。
読みやすく書いたつもりなので、ぜひコードを読んでみてください。

<details>
<summary>ソースコード</summary>

```js
/**
  * 多重集合の最大値ライブラリ
  */
class MultisetMax {
    capacity;
    length;
    map;
    // 典型的なセグメント木の実装と同様に、 `tree[1]` から `tree[capacity - 1]` までは集約値が入ります。特に、 `tree[1]` はすべての要素の最大値となります。
    // `tree[capacity]` から `tree[capacity + length - 1]` までは要素の値です。
    tree;

    constructor() {
        this.capacity = 128;
        this.length = 0;
        this.map = new Map;
        this.tree = new Array(this.capacity * 2).fill(0);
    }

    /**
      * 値 `x` を多重集合に追加する。
      * @param x 追加する値
      * 計算量: amortized O(log(this.length)), worst O(this.length)
      */
    add(x) {
        if(!this.map.has(x)) {
            if(this.length == this.capacity) {
                this.tree.length = this.capacity * 4;
                this.tree.fill(0, this.capacity * 2);
                this.tree.copyWithin(this.capacity * 2, this.capacity, this.capacity * 2);
                this.capacity *= 2;
                for(let i = this.capacity; --i > 0; ) this.tree[i] = Math.max(this.tree[i * 2], this.tree[i * 2 + 1]);
            }
            const index = this.length++;
            this.map.set(x, {index, count: 0});
        }
        const entry = this.map.get(x);
        if(entry.count++ == 0) {
            let i = this.capacity + entry.index;
            this.tree[i] = x;
            i >>= 1;
            while(i > 0) {
                this.tree[i] = Math.max(this.tree[i * 2], this.tree[i * 2 + 1]);
                i >>= 1;
            }
        }
    }

    /**
      * 値 `x` を多重集合から削除する。
      * @param x 削除する値
      * 計算量: worst O(log(this.length))
      */
    remove(x) {
        if(!this.map.has(x)) return;
        const entry = this.map.get(x);
        if(entry.count == 0) return;
        if(--entry.count == 0) {
            let i = this.capacity + entry.index;
            this.tree[i] = 0;
            i >>= 1;
            while(i > 0) {
                this.tree[i] = Math.max(this.tree[i * 2], this.tree[i * 2 + 1]);
                i >>= 1;
            }
        }
    }


    /**
      * 多重集合に含まれている値の最大値を求める。
      * 計算量: worst O(1)
      */
    get max() {
        return this.tree[1];
    }
}

// `(yield)` で行入力
function* main() {
    const [N, M, Q] = (yield).split(' ').map(Number);

    const graph = new Array(N).fill().map(() => []);
    const inGroup = new Array(N).fill(false);
    const relation = new Array(M);
    const relationIsBorder = new Array(M).fill(false);
    const relationValue = [];
    for(let relationId = 0; relationId < M; relationId++) {
        const [_a, _b, f] = (yield).split(' ').map(Number);
        const [a, b] = [_a - 1, _b - 1];
        relation[relationId] = [a, b];
        relationValue[relationId] = f;
        graph[a].push(relationId);
        graph[b].push(relationId);
    }

    const borderValues = new MultisetMax;
    for(let i = 0; i < Q; i++) {
        const [op, _q] = (yield).split(' ');
        const q = +_q - 1;
        inGroup[q] = (op == '+');
        for(const relationId of graph[q]) {
            const [a, b] = relation[relationId];
            const isBorderNow = (inGroup[a] != inGroup[b]);
            if(isBorderNow != relationIsBorder[relationId]) {
                const value = relationValue[relationId];
                if (isBorderNow) borderValues.add(value);
                else borderValues.remove(value);
                relationIsBorder[relationId] = isBorderNow;
            }
        }
        console.log(borderValues.max);
    }
}

const mainIterator = main();
mainIterator.next();
require('readline').createInterface({input: process.stdin}).on('line', line => {
    mainIterator.next(line);
});
```
</details>