Notification [第五回 アルゴリズム実技検定 O]

https://atcoder.jp/contests/past202012-open/tasks/past202012_o

前提知識

• 平方分割

解説

https://atcoder.jp/contests/past202012-open/submissions/22306825

平方分割ではないかもしれないが、雰囲気は似ているのでとりあえず入れておく。
かなりテクニカルな方針。
特に必要な知識があるものではないが、ブレイクスルーが必要な発想。

気が付くべきこと

直接友達関係を持つユーザーがsqrt(M)以上いるユーザーは高々sqrt(M)人しか存在しない。
言われてみればそうなのだが、これがどのように計算量改善に結びつくのだろうか。

T=1で直接友人関係を持つユーザーがsqrt(M)未満であれば、そのまま友達関係にあるユーザーに通知をインクリメントしていけばいい。
sent[to] := toさんに贈られた通知の個数
これを用意しておいて、これをインクリメントするだけでいい。

問題が、直接友人関係を持つユーザーがsqrt(M)以上の場合である。
少し見方を変えると、ある人の友人の中で友人関係を持つユーザーがsqrt(M)以上の友人の数もsqrt(M)以下である。
なので、この場合は、直接友人に通知をインクリメントするのではなく、その人が一斉発信した通知の件数をインクリメントしておく。
recv[to] := toさんから一斉発信された通知の件数
これを用意しておいて、T=2の時にその人の友人の中で友人関係を持つユーザーがsqrt(M)以上のすべての友人についてrecv[to]を確認して、
まだ確認してない通知の件数を答えに追加して答えればいい。

実装

特に注意点はない。recvについて各友人で受け取り済みの通知の件数は違うので、自分の実装では適当にvectorで
sqrt(M)以上の友人を管理するだけでなく、vector<pair<int,int>>として、受け取り済みの通知の件数も保持するようにしている。
他は説明したようなことを実装する。

計算量

T=1でもT=2でも最大でループはsqrt(M)回なので、O(Qsqrt(M))となり、これは間に合う。

int N, M, Q;
vector<int> E[201010];
int send[201010], recv[201010];
int LIM = sqrt(201010);
vector<pair<int,int>> great[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }
    rep(i, 0, N) if (LIM <= E[i].size()) fore(to, E[i]) great[to].push_back({ i, 0 });
    cin >> Q;
    rep(_, 0, Q) {
        int T, x; cin >> T >> x; x--;

        if (T == 1) {
            if (E[x].size() <= LIM) {
                fore(to, E[x]) send[to]++;
            }
            else {
                recv[x]++;
            }
        }
        else {
            int ans = send[x]; send[x] = 0;
            fore(p, great[x]) {
                ans += recv[p.first] - p.second;
                p.second = recv[p.first];
            }
            printf("%d\n", ans);
        }
    }

}