問題概要

$N$頂点0辺の無向グラフがある。このグラフに$Q$回辺が追加されたり削除されたりする(指定された箇所に辺が無ければ追加、あれば削除)。
「各辺の両端の頂点の次数の積」の和をQ回それぞれ求めよ。

制約

$1 \leqq N \leqq 10^{5}$
$1 \leqq Q \leqq 10^{5}$

解法

辺についての積の和　→　頂点についての和の積として考えることができます。
ある頂点$u$が答えに寄与する値$W_u$は、$u$と直接辺でつながれている頂点の集合を$S$、頂点$x$の次数を$d_x$とすると
$$W_u = d_u\displaystyle \sum_{v \in S}^{} d_v$$ となり、「和の積」の形になります。

以降の$u,v$はクエリで与えられた2頂点を指します。
各頂点について「その頂点とつながっている頂点の次数の和」を保持しながら差分更新することを考えます。
追加(削除)によってそれらの値が変わる箇所は、頂点$u,v$と隣接する頂点です。
よって愚直に更新しようとすると次数が大きい頂点に辺の追加や削除がされると計算量が増大します。

ここで2パターンに分けて考えます。

頂点$u,v$
頂点$u,v$と隣接する頂点($u,v$以外)

別々にした方が頭が壊れにくいと思いました(たぶん)。~~平方分割、頭壊れやすい気がする…~~

①頂点$u,v$

追加される際は「追加後の$u$の次数」と「追加後の$v$の次数」の積がそのまま加算されます。削除されるときは逆で、削除前のそれぞれの頂点の次数の積が差し引かれます。

②頂点$u,v$と隣接する頂点

唐突ですが、頂点を特殊な頂点と一般の頂点に分けます(以降は青(の頂点)、黒(の頂点)と呼ぶことにします)

青の選定基準は、
「$\sqrt Q$回以上クエリで登場している」
です。
青は最大でも$2\sqrt Q$個しか存在しません(クエリで与えられる数字の数が$2Q$個であるため)

各クエリの中で、青と黒で全く異なる操作を行います。それぞれの操作は以下の通りです。
青…上記で述べた「その頂点とつながっている頂点の次数の和」を陽に管理して差分更新を行う。

黒…和を持たずに、クエリごとに毎回隣接頂点の情報を調べ上げて差分更新を行う。

操作の具体的な説明の前に、このように頂点を分けることによって計算量が改善されるのかを先に明らかにします。

頂点を分けることによる嬉しさ

青、黒それぞれについて各クエリごとの計算量を確認します。

青…次数こそ多いものの、和を管理しているので計算は$O(1)$でできます。更新ですが、色を分けたことによって黒の頂点についてはそもそも情報を持たないため、更新する必要がないのです。これが大きく、青の頂点は高々$2\sqrt Q$個なので、更新は$O(\sqrt Q)$で完了します。

黒…クエリに$\sqrt Q$回以上登場していないので、当然次数は$\sqrt Q$未満です。よって求値や更新が$O(\sqrt Q)$でできます。

よってクエリあたり$O(\sqrt Q)$の計算量で抑えられ、全体計算量が$O(Q \sqrt Q)$で済むことになります。

平方分割、考察かなり進めないとどうして計算量落ちるのか分からないがち…(慣れていないだけかも)

具体的な操作

「嬉しさ」のところで述べたところを実装に移していくことを考えます。

削除は追加と逆の操作をすればよいので、追加クエリのみを考えることにします。また$u$と$v$で操作が変わらないので、頂点は$u$とします
ここまでの説明で用いた「ある頂点とつながっている頂点の次数の和」を$sum$とします。

$u$が青のとき

答えに$sum$を加算($u$の次数が1増えるため、$1 × sum$分だけ増える)
$sum$に$v$の次数を加算する。$v$の次数はクエリ前より1増えていることに注意。
$u$と隣接する青い頂点について、$sum$を1増やす($u$の次数が$1$増えるため)
$u$の隣接する頂点リストに$v$を追加する

$u$が黒のとき

隣接する頂点の和を愚直に調べて取得し、答えに加算
$u$と隣接する青い頂点について、$sum$を1増やす
$u$の隣接する頂点リストに$v$を追加する

ここで、隣接する頂点を見る際に$v$は見ないようにします(追加する時は追加する前に、削除する時は削除した後に操作を行う)
$v$でも同様の操作を行った後、最後に$u$の次数と$v$の次数の積を加算(減算)します。

実装上の注意・バグりそうなところ

青だけを更新するため、隣接頂点リストの中でも「隣接頂点 : 青」、「隣接頂点 : 黒」に分けておく
$u,v$が青かどうかを高速に判断したいため、setもしくはvectorで青リストを作成して、二分探索で存在判定(vectorの場合はソートを忘れずに)
$u$の隣接頂点リストに$v$を追加すると、$u$の次数が1増えた状態で取得される

実装

#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;

int main(){
    int N,Q; cin >> N >> Q;
    int q = 320;
    vector<int> u(Q), v(Q), cnt(N,0);
    for(int i=0; i<Q; i++){
        cin >> u[i] >> v[i]; u[i]--; v[i]--;
        cnt[u[i]]++;
        cnt[v[i]]++;
    }
    set<int> sp; //特殊頂点をsetで管理
    for(int i=0; i<N; i++){
        if(cnt[i] >= q) sp.insert(i);
    }
    ll ans = 0;
    vector<int> sum(N,0); //隣接頂点の次数の和(特殊頂点のみ使用)
    vector<set<int>> ads(N), adn(N); //隣接頂点を管理 特殊/一般

    //先に追加・削除の処理をラムダ式で記述
    auto ins_sp = [&](int node, int sz){
        ans += sum[node];
        sum[node] += sz;
        for(auto x : ads[node]) sum[x]++;
    };
    auto del_sp = [&](int node, int sz){
        sum[node] -= sz;
        ans -= sum[node];
        for(auto x : ads[node]) sum[x]--;
    };
    auto ins_nor = [&](int node){
        ll s = 0;
        for(auto x : ads[node]) s += ads[x].size() + adn[x].size();
        for(auto x : adn[node]) s += ads[x].size() + adn[x].size();
        ans += s;
        for(auto x : ads[node]) sum[x]++;
    };
    auto del_nor = [&](int node){
        ll s = 0;
        for(auto x : ads[node]) s += ads[x].size() + adn[x].size();
        for(auto x : adn[node]) s += ads[x].size() + adn[x].size();
        ans -= s;
        for(auto x : ads[node]) sum[x]--;
    };

    set<pair<int,int>> query;
    for(int i=0; i<Q; i++){
        //頂点uの処理
        ll sz = ads[v[i]].size() + adn[v[i]].size();
        if(query.count({u[i],v[i]})){
            if(sp.count(v[i])) ads[u[i]].erase(v[i]);
            else adn[u[i]].erase(v[i]);
            if(sp.count(u[i])) del_sp(u[i], sz);
            else del_nor(u[i]);
        }else{
            if(sp.count(u[i])) ins_sp(u[i], sz + 1);
            else ins_nor(u[i]);
            if(sp.count(v[i])) ads[u[i]].insert(v[i]);
            else adn[u[i]].insert(v[i]);
        }

        //頂点vの処理
        sz = ads[u[i]].size() + adn[u[i]].size();
        if(query.count({u[i],v[i]})){
            if(sp.count(u[i])) ads[v[i]].erase(u[i]);
            else adn[v[i]].erase(u[i]);
            if(sp.count(v[i])) del_sp(v[i], sz + 1);
            else del_nor(v[i]);
            query.erase({u[i], v[i]});
            ans -= (sz + 1) * (ads[v[i]].size() + adn[v[i]].size() + 1);
        }else{
            if(sp.count(v[i])) ins_sp(v[i], sz);
            else ins_nor(v[i]);
            if(sp.count(u[i])) ads[v[i]].insert(u[i]);
            else adn[v[i]].insert(u[i]);
            query.insert({u[i], v[i]});
            ans += sz * (ads[v[i]].size() + adn[v[i]].size());
        }

        cout << ans << "\n";
    }
}

suta精進記

競プロ関連体験記や精進記録などを書きます

ACPC2020 Day2 J : DEG MUL SUM