- 初回考察
- プッシュでもプルでも最悪10^5になるので10^5回のクエリでは破綻する
- (補足: 通知発生時に受領者の値を変更する「プッシュ」の場合、フレンドの10^5人いる人が通知を10^5回送るとダメ。逆に通知確認の時にフレンドの誰が送ったか確認しにいく「プル」の場合はフレンドの多い人が通知確認をしまくるとダメ)
- 平方分割
- フレンドがルートN以上の人の処理だけ遅延させる
- こういう人は高々ルートN人
- 通知確認時にこれらの人xだけプルする
- xの発生させた総通知数をxが持つ
- yがxから受信した総数をyが持つ。高々ルートN
- この二つを引けばxからの新しい通知の数がわかる
- 考察完了
- 公式解説
- 平方分割でOK