0715.cpp (2016B)
1 class SegmentTree { 2 struct Node { 3 Node *left = nullptr; 4 Node *right = nullptr; 5 int low; 6 int high; 7 int value; 8 9 Node(int low, int high, int value) : low(low), high(high), value(value) {} 10 } root; 11 12 void update(Node *root, int l, int r, int val) { 13 if (root->low == l && root->high == r) { 14 root->value = val; 15 root->left = root->right = NULL; // memory leak; 16 return; 17 } 18 19 const int mid = root->low + (root->high - root->low) / 2; 20 21 if (!root->left) { 22 root->left = new Node(root->low, mid, root->value); 23 root->right = new Node(mid + 1, root->high, root->value); 24 } 25 26 if (r <= mid) 27 update(root->left, l, r, val); 28 else if (l > mid) 29 update(root->right, l, r, val); 30 else 31 update(root->left, l, mid, val), update(root->right, mid + 1, r, val); 32 root->value = root->left->value && root->right->value; 33 } 34 35 bool query(const Node *root, int l, int r) const { 36 if (!root->left) return root->value; 37 if (root->low == l && root->high == r) return root->value; 38 39 const int mid = root->low + (root->high - root->low) / 2; 40 41 if (r <= mid) 42 return query(root->left, l, r); 43 else if (l > mid) 44 return query(root->right, l, r); 45 return query(root->left, l, mid) && query(root->right, mid + 1, r); 46 } 47 48 public: 49 SegmentTree(int l, int r, int val) : root(l, r, val) {} 50 51 void update(int l, int r, int val) { return update(&root, l, r, val); } 52 bool query(int l, int r) const { return query(&root, l, r); } 53 }; 54 55 class RangeModule { 56 SegmentTree seg; 57 58 public: 59 RangeModule() : seg(0, 1e9, 0) {} 60 61 void addRange(int left, int right) { seg.update(left, right - 1, 1); } 62 63 bool queryRange(int left, int right) { return seg.query(left, right - 1); } 64 65 void removeRange(int left, int right) { seg.update(left, right - 1, 0); } 66 };