結果

問題 No.1788 Same Set
コンテスト
ユーザー Nachia
提出日時 2021-12-17 01:38:03
言語 Text
(cat 8.3)
結果
WA  
実行時間 -
コード長 612 bytes
コンパイル時間 135 ms
コンパイル使用メモリ 6,944 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-14 01:48:20
合計ジャッジ時間 1,804 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

時空間上の矩形に作用するオフラインクエリは、個数を O(log n) 倍にして rollback 可能データ構造用のクエリに変換できます。
このテクニックは特に offline dynamic connectivity を rollback 可能 disjoint set union 用クエリに変換するときに用いられます。 (https://nyaannyaan.github.io/library/graph/offline-dynamic-connectivity.hpp)

禁止区間は時空間上の矩形 0 埋め、数え上げは総和なので、遅延セグ木で管理でき、枝刈りが効く場合があります。
時間 O(N log^2 N) 、空間 O(N log N) です。
0