かなり古い企業コンの問題です。点数はついていませんが、感覚では500ぐらいかなと思います。

問題概要

$2 \le n \le 100000$ 頂点のグラフが与えられます。はじめグラフには辺がまったく張られていません。 $0 \le m \le 100000$ 個のクエリが与えられます。クエリには以下の3種類があります。

tweet $u$ : 頂点 $u$ および隣接する頂点のポイントを1増やす
follow $u, v$ : 辺 $(u, v)$ を張る
unfollow $u, v$ : 辺 $(u, v)$ を削除する

$m$ 個のクエリを処理した後、それぞれの頂点のポイントを答えよ。

解説

誤読防止のためにあえて書いておきますが、タイプ1のクエリでは、連結成分に+1するのではなくて自分自身および隣接する頂点を対象とします。

クエリ1がくるたびに毎回隣接する頂点を列挙してインクリメントしていくのは $O(nm)$ かかり間に合いません。 unfollowするときに差分を一気に更新するようなアルゴリズムを考えます（与えられたすべてのクエリを処理し終わった後、今張られている辺をすべて削除するまでunfollowを繰り返すようなクエリを追加したとしても答えは変わりません）。

さて、unfollow $u, v$ されたとしましょう。このとき、いつかにfollow $u, v$ が呼ばれたわけですが、そのときの $v$ のポイントをhogeとします。unfollowまでにhogeがhoge+nになったとすると、unfollow時に $u$ のポイントをn増やせばいいですね。

これをするには、実はどのタイミングで $(u, v)$ の辺が張られたかなどを記録せずとも、 followされた瞬間に $u$ のポイントを-hogeし、unfollowされた瞬間に（その瞬間の $v$ のポイント、すなわちhoge+n）を加えればいいです。

実装

原題は、 $k$ 番目に多いポイントを答えよ、という問題だったので最後に結果をソートしてます。

int tw[101010];
int dif[101010];
set<ii> edges;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        char c;
        cin >> c;
        if (c == 't') {
            int u;
            cin >> u;
            tw[u]++;
            dif[u]++;
        } else if (c == 'f') {
            int u, v;
            cin >> u >> v;
            edges.insert(ii(min(u, v), max(u, v)));
            tw[u] -= dif[v];
            tw[v] -= dif[u];
        } else {
            int u, v;
            cin >> u >> v;
            edges.erase(ii(min(u, v), max(u, v)));
            tw[u] += dif[v];
            tw[v] += dif[u];
        }
    }
    for (ii edge: edges) {
        int u = edge.first, v = edge.second;
        tw[u] += dif[v];
        tw[v] += dif[u];
    }
    vi ans;
    for (int i = 1; i <= n; i++) {
        ans.push_back(tw[i]);
    }
    sort(ans.begin(), ans.end(), greater<>());
    cout << ans[k - 1] << endl;
}