This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "ds/offline_query/add_remove_query.hpp"
/* ・時刻 t に x を追加する ・時刻 t に x を削除する があるときに, ・時刻 [l, r) に x を追加する に変換する. 同じキーが複数回来ると困るので適当なラベルをつけておこう. */ template <typename X, bool monotone> struct Add_Remove_Query { map<X, int> MP; vc<tuple<int, int, X>> dat; map<X, vc<int>> ADD; map<X, vc<int>> RM; void add(int time, X x) { if (monotone) return add_monotone(time, x); ADD[x].eb(time); } void remove(int time, X x) { if (monotone) return remove_monotone(time, x); RM[x].eb(time); } // すべてのクエリが終わった現在時刻を渡す vc<tuple<int, int, X>> calc(int time) { if (monotone) return calc_monotone(time); vc<tuple<int, int, X>> dat; for (auto&& [x, A]: ADD) { vc<int> B; if (RM.count(x)) { B = RM[x]; RM.erase(x); } if (len(B) < len(A)) B.eb(time); assert(len(A) == len(B)); sort(all(A)); sort(all(B)); FOR(i, len(A)) { assert(A[i] <= B[i]); if (A[i] < B[i]) dat.eb(A[i], B[i], x); } } assert(len(RM) == 0); return dat; } private: void add_monotone(int time, X x) { assert(!MP.count(x)); MP[x] = time; } void remove_monotone(int time, X x) { auto it = MP.find(x); assert(it != MP.end()); int t = (*it).se; MP.erase(it); if (t == time) return; dat.eb(t, time, x); } vc<tuple<int, int, X>> calc_monotone(int time) { for (auto&& [x, t]: MP) { if (t == time) continue; dat.eb(t, time, x); } return dat; } };
#line 1 "ds/offline_query/add_remove_query.hpp" /* ・時刻 t に x を追加する ・時刻 t に x を削除する があるときに, ・時刻 [l, r) に x を追加する に変換する. 同じキーが複数回来ると困るので適当なラベルをつけておこう. */ template <typename X, bool monotone> struct Add_Remove_Query { map<X, int> MP; vc<tuple<int, int, X>> dat; map<X, vc<int>> ADD; map<X, vc<int>> RM; void add(int time, X x) { if (monotone) return add_monotone(time, x); ADD[x].eb(time); } void remove(int time, X x) { if (monotone) return remove_monotone(time, x); RM[x].eb(time); } // すべてのクエリが終わった現在時刻を渡す vc<tuple<int, int, X>> calc(int time) { if (monotone) return calc_monotone(time); vc<tuple<int, int, X>> dat; for (auto&& [x, A]: ADD) { vc<int> B; if (RM.count(x)) { B = RM[x]; RM.erase(x); } if (len(B) < len(A)) B.eb(time); assert(len(A) == len(B)); sort(all(A)); sort(all(B)); FOR(i, len(A)) { assert(A[i] <= B[i]); if (A[i] < B[i]) dat.eb(A[i], B[i], x); } } assert(len(RM) == 0); return dat; } private: void add_monotone(int time, X x) { assert(!MP.count(x)); MP[x] = time; } void remove_monotone(int time, X x) { auto it = MP.find(x); assert(it != MP.end()); int t = (*it).se; MP.erase(it); if (t == time) return; dat.eb(t, time, x); } vc<tuple<int, int, X>> calc_monotone(int time) { for (auto&& [x, t]: MP) { if (t == time) continue; dat.eb(t, time, x); } return dat; } };