苦手系の問題だけど、解けてよかった。
問題概要
正の整数 が与えられる。はじめ空である集合
が与えられるので、次のクエリに答えよ。
- クエリタイプ
1 x：集合に整数値
がない場合は挿入し、ある場合は削除する
- クエリタイプ
2 x：集合以下である要素間には辺が張られるグラフを考えたとき、整数値
制約
考えたこと
まず、クエリ先読みして、座標圧縮することにする (座標圧縮したときの番号を、その要素の座標と呼ぶことにする)。そして、各要素について次の値を管理することとした。
num[v]← 座標値がであるような要素が
left[v]← 座標値がright[v]← 座標値が
これらの値を正しく管理できていれば、num を BIT で実現することによって、クエリ 2 には答えられる。つまり、配列 num の区間 [left[v], right[v] + 1) の総和を総和を求めればよい。
left と right の更新については、「区間値更新」がしたいとなる。たとえば、集合 に座標値
の要素を挿入するとき、それによって
の前後の要素 (
と
とする) の間に辺が張られていなかったのが、張られるようになったときには、
- 区間 [
left[p],right[q]+ 1) 全体について、leftの値をleft[p]に更新するrightの値をright[q]に更新する
ということがしたい。こうしたことは遅延評価セグメント木で実現できる。なお、 から要素を削除する場合についても、同様に考察できる。
全体の計算量は となる。
コード
#include <bits/stdc++.h> using namespace std; template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); } template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); } // BIT を用いた集合型 template<class Abel> struct FastMultiSetByBIT { int topbit(int x) const { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int lowbit(int x) const { return (x == 0 ? -1 : __builtin_ctz(x)); } int lim; Abel IDENTITY; vector<Abel> dat; // [0, n) FastMultiSetByBIT(int n, Abel identity = 0) : lim(n), IDENTITY(identity), dat(n, identity) { } void init(int n, Abel identity = 0) { lim = n; IDENTITY = identity; dat.assign(n, IDENTITY); } // p is 0-indexed void add(int p, Abel x) { if (p < 0) p = 0; for (int i = p; i < (int)dat.size(); i |= i + 1) dat[i] = dat[i] + x; } // [0, p), p is 0-indexed Abel sum(int p) const { if (p > lim) p = lim; Abel res = IDENTITY; for (int i = p - 1; i >= 0; i = (i & (i + 1)) - 1) res = res + dat[i]; return res; } // [l, r), l and r are 0-indexed Abel sum(int l, int r) const { return sum(r) - sum(l); } // insert, erase, count, min, max void insert(int x) { add(x, 1); } void erase(int x) { if (count(x)) add(x, -1); } Abel count(int x) const { return sum(x, x + 1); } Abel count(int l, int r) const { return sum(l, r); } Abel size() const { return sum(lim); } bool operator [] (int x) const { return count(x); } int get_min() const { return next(); } int get_max() const { return prev(); } // get max r s.t. check(sum(l, r)) = True (0-indexed), O(log N) // check(IDENTITY) must be True int max_right(const function<bool(Abel)> check, int l = 0) const { if (l >= lim) return lim; assert(check(IDENTITY)); Abel s = IDENTITY; int k = 0; while (true) { if (l % 2 == 1) s = s - dat[l - 1], --l; if (l <= 0) { k = topbit(lim) + 1; break; } k = lowbit(l) - 1; if (l + (1 << k) > lim) break; if (!check(s + dat[l + (1 << k) - 1])) break; s = s - dat[l - 1]; l -= l & -l; } while (k) { --k; if (l + (1 << k) - 1 < lim) { Abel ns = s + dat[l + (1 << k) - 1]; if (check(ns)) { l += (1 << k); s = ns; } } } return l; } // get min l s.t. check(sum(l, r)) = True (0-indexed), O(log N) // check(IDENTITY) must be True int min_left(const function<bool(Abel)> check, int r = -1) const { if (r == -1) r = lim; if (r <= 0) return 0; assert(check(IDENTITY)); Abel s = IDENTITY; int k = 0; while (r > 0 && check(s)) { s = s + dat[r - 1]; k = lowbit(r); r -= r & -r; } if (check(s)) return 0; while (k) { --k; Abel ns = s - dat[r + (1 << k) - 1]; if (!check(ns)) { r += (1 << k); s = ns; } } return r + 1; } // k-th number that is not less than l (k is 0-indexed) int get(Abel k, int l = 0) const { return max_right([&](Abel x) { return x <= k; }, l); } // next (including x) int next(int l = 0) const { if (l < 0) l = 0; if (l > lim) l = lim; return max_right([&](Abel x) { return x <= 0; }, l); } // prev (including x) int prev(int r) const { if (r > lim) r = lim; return min_left([&](Abel x) { return x <= 0; }, r + 1) - 1; } int prev() const { prev(lim); } // debug friend ostream& operator << (ostream &s, const FastMultiSetByBIT &fs) { for (int x = fs.get_min(); x < fs.lim; x = fs.next(x + 1)) { s << x << " "; } return s; } }; // Lazy Segment Tree template<class Monoid, class Action> struct LazySegmentTree { // various function types using FuncMonoid = function<Monoid(Monoid, Monoid)>; using FuncAction = function<Monoid(Action, Monoid)>; using FuncComposition = function<Action(Action, Action)>; // core member int N; FuncMonoid OP; FuncAction ACT; FuncComposition COMP; Monoid IDENTITY_MONOID; Action IDENTITY_ACTION; // inner data int log, offset; vector<Monoid> dat; vector<Action> lazy; // constructor LazySegmentTree() {} LazySegmentTree(int n, const FuncMonoid op, const FuncAction act, const FuncComposition comp, const Monoid &identity_monoid, const Action &identity_action) { init(n, op, act, comp, identity_monoid, identity_action); } LazySegmentTree(const vector<Monoid> &v, const FuncMonoid op, const FuncAction act, const FuncComposition comp, const Monoid &identity_monoid, const Action &identity_action) { init(v, op, act, comp, identity_monoid, identity_action); } void init(int n, const FuncMonoid op, const FuncAction act, const FuncComposition comp, const Monoid &identity_monoid, const Action &identity_action) { N = n, OP = op, ACT = act, COMP = comp; IDENTITY_MONOID = identity_monoid, IDENTITY_ACTION = identity_action; log = 0, offset = 1; while (offset < N) ++log, offset <<= 1; dat.assign(offset * 2, IDENTITY_MONOID); lazy.assign(offset * 2, IDENTITY_ACTION); } void init(const vector<Monoid> &v, const FuncMonoid op, const FuncAction act, const FuncComposition comp, const Monoid &identity_monoid, const Action &identity_action) { init((int)v.size(), op, act, comp, identity_monoid, identity_action); build(v); } void build(const vector<Monoid> &v) { assert(N == (int)v.size()); for (int i = 0; i < N; ++i) dat[i + offset] = v[i]; for (int k = offset - 1; k > 0; --k) pull_dat(k); } int size() const { return N; } // basic functions for lazy segment tree void pull_dat(int k) { dat[k] = OP(dat[k * 2], dat[k * 2 + 1]); } void apply_lazy(int k, const Action &f) { dat[k] = ACT(f, dat[k]); if (k < offset) lazy[k] = COMP(f, lazy[k]); } void push_lazy(int k) { apply_lazy(k * 2, lazy[k]); apply_lazy(k * 2 + 1, lazy[k]); lazy[k] = IDENTITY_ACTION; } void pull_dat_deep(int k) { for (int h = 1; h <= log; ++h) pull_dat(k >> h); } void push_lazy_deep(int k) { for (int h = log; h >= 1; --h) push_lazy(k >> h); } // setter and getter, update A[i], i is 0-indexed, O(log N) void set(int i, const Monoid &v) { assert(0 <= i && i < N); int k = i + offset; push_lazy_deep(k); dat[k] = v; pull_dat_deep(k); } Monoid get(int i) { assert(0 <= i && i < N); int k = i + offset; push_lazy_deep(k); return dat[k]; } Monoid operator [] (int i) { return get(i); } // apply f for index i void apply(int i, const Action &f) { assert(0 <= i && i < N); int k = i + offset; push_lazy_deep(k); dat[k] = ACT(f, dat[k]); pull_dat_deep(k); } // apply f for interval [l, r) void apply(int l, int r, const Action &f) { assert(0 <= l && l <= r && r <= N); if (l == r) return; l += offset, r += offset; for (int h = log; h >= 1; --h) { if (((l >> h) << h) != l) push_lazy(l >> h); if (((r >> h) << h) != r) push_lazy((r - 1) >> h); } int original_l = l, original_r = r; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) apply_lazy(l++, f); if (r & 1) apply_lazy(--r, f); } l = original_l, r = original_r; for (int h = 1; h <= log; ++h) { if (((l >> h) << h) != l) pull_dat(l >> h); if (((r >> h) << h) != r) pull_dat((r - 1) >> h); } } // get prod of interval [l, r) Monoid prod(int l, int r) { assert(0 <= l && l <= r && r <= N); if (l == r) return IDENTITY_MONOID; l += offset, r += offset; for (int h = log; h >= 1; --h) { if (((l >> h) << h) != l) push_lazy(l >> h); if (((r >> h) << h) != r) push_lazy(r >> h); } Monoid val_left = IDENTITY_MONOID, val_right = IDENTITY_MONOID; for (; l < r; l >>= 1, r >>= 1) { if (l & 1) val_left = OP(val_left, dat[l++]); if (r & 1) val_right = OP(dat[--r], val_right); } return OP(val_left, val_right); } Monoid all_prod() { return dat[1]; } // get max r that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int max_right(const function<bool(Monoid)> f, int l = 0) { if (l == N) return N; l += offset; push_lazy_deep(l); Monoid sum = IDENTITY_MONOID; do { while (l % 2 == 0) l >>= 1; if (!f(OP(sum, dat[l]))) { while (l < offset) { push_lazy(l); l = l * 2; if (f(OP(sum, dat[l]))) { sum = OP(sum, dat[l]); ++l; } } return l - offset; } sum = OP(sum, dat[l]); ++l; } while ((l & -l) != l); // stop if l = 2^e return N; } // get min l that f(get(l, r)) = True (0-indexed), O(log N) // f(IDENTITY) need to be True int min_left(const function<bool(Monoid)> f, int r = -1) { if (r == 0) return 0; if (r == -1) r = N; r += offset; push_lazy_deep(r - 1); Monoid sum = IDENTITY_MONOID; do { --r; while (r > 1 && (r % 2)) r >>= 1; if (!f(OP(dat[r], sum))) { while (r < offset) { push_lazy(r); r = r * 2 + 1; if (f(OP(dat[r], sum))) { sum = OP(dat[r], sum); --r; } } return r + 1 - offset; } sum = OP(dat[r], sum); } while ((r & -r) != r); return 0; } // debug stream friend ostream& operator << (ostream &s, LazySegmentTree seg) { for (int i = 0; i < (int)seg.size(); ++i) { s << seg[i]; if (i != (int)seg.size() - 1) s << " "; } return s; } // dump void dump() { for (int i = 0; i <= log; ++i) { for (int j = (1 << i); j < (1 << (i + 1)); ++j) { cout << "{" << dat[j] << "," << lazy[j] << "} "; } cout << endl; } } }; #define DEBUG 1 #define COUT(x) if (DEBUG) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) { return s << '<' << P.first << ", " << P.second << '>'; } template<class T> ostream& operator << (ostream &s, vector<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, deque<T> P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template<class T> ostream& operator << (ostream &s, vector<vector<T> > P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template<class T> ostream& operator << (ostream &s, set<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T> ostream& operator << (ostream &s, multiset<T> P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } int main() { // 入力と座標圧縮 long long Q, K; cin >> Q >> K; vector<long long> type(Q), X(Q), v(Q), alt; for (int i = 0; i < Q; ++i) { cin >> type[i] >> X[i]; alt.push_back(X[i]); } sort(alt.begin(), alt.end()); alt.erase(unique(alt.begin(), alt.end()), alt.end()); for (int i = 0; i < Q; ++i) { v[i] = lower_bound(alt.begin(), alt.end(), X[i]) - alt.begin(); } // N 未満の非負整数値を管理する集合型 int N = alt.size(); FastMultiSetByBIT<long long> fs(N); // 遅延評価セグメント木 auto op = [&](int a, int b) { return max(a, b); }; auto mapping = [&](int f, int x) { return (f == -1 ? x : f); }; auto composition = [&](int g, int f) { return (g == -1 ? f : g); }; const int NUL = -10; LazySegmentTree<int, int> left(N, op, mapping, composition, NUL, -1); LazySegmentTree<int, int> right(N, op, mapping, composition, NUL, -1); // クエリ処理 for (int q = 0; q < Q; ++q) { int cur = v[q]; int pre = fs.prev(cur-1), nex = fs.next(cur+1); if (type[q] == 1) { if (!fs.count(cur)) { // S が alt[cur] を持たないとき fs.insert(cur); int l = cur, r = cur; if (pre >= 0 && alt[cur] - alt[pre] <= K) chmin(l, left[pre]); if (nex < N && alt[nex] - alt[cur] <= K) chmax(r, right[nex]); left.apply(l, r + 1, l), right.apply(l, r + 1, r); } else { // S が alt[cur] を持つとき fs.erase(cur); int l = cur, r = cur; if (pre >= 0 && alt[cur] - alt[pre] <= K) chmin(l, left[pre]); if (nex < N && alt[nex] - alt[cur] <= K) chmax(r, right[nex]); if (pre < 0) { left.apply(0, nex, NUL), right.apply(0, nex, NUL); if (nex < r+1) left.apply(nex, r+1, nex); } else if (nex >= N) { left.apply(pre+1, N, NUL), right.apply(pre+1, N, NUL); if (l < pre+1) right.apply(l, pre+1, pre); } else if (alt[nex] - alt[pre] > K) { left.apply(pre+1, nex, -1), right.apply(pre+1, nex, -1); if (nex < r+1) left.apply(nex, r+1, nex); if (l < pre+1) right.apply(l, pre+1, pre); } } } else { int l = left[cur], r = right[cur]; cout << fs.count(l, r + 1) << endl; } } }
