区間をsetで管理するやつ (daylight/structure/range_set.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/structure/range_set.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)
• daylight/range.hpp

Verified with

• test/aoj/others/2880.test.cpp
• test/yukicoder/674.test.cpp

Code

#pragma once
#include "daylight/base.hpp"
#include "daylight/range.hpp"

/// @brief 区間をsetで管理するやつ
template<typename T = ll>
struct RangeSet {
private:
	set<Range<T>> ranges;

public:
	RangeSet() {
	}

	/// @brief 区間を追加する
	optional<Range<T>> add(Range<T> r) {
		if(contains(r) || r.empty()) return nullopt;
		auto it = ranges.lower_bound(r);
		if(it != ranges.begin()) {
			it--;
			if(it->contact(r)) {
				r.extendLeft(*it);
				ranges.erase(it);
			}
		}
		vector<Range<T>> to_erase;
		it = ranges.lower_bound(r);
		while(true) {
			if(it == ranges.end()) break;
			if(!r.contact(*it)) break;
			r.extendRight(*it);
			to_erase.push_back(*it);
			it++;
		}
		for(auto &e: to_erase) ranges.erase(e);
		ranges.insert(r);
		return r;
	}

	void remove(Range<T> r) {
		typename decltype(ranges)::iterator it
			= ranges.lower_bound(r);
		vector<Range<T>> to_erase;
		vector<Range<T>> to_insert;
		if(it != ranges.begin()) {
			it--;
			auto xa = r.getLeft();
			auto xb = it->getRight();
			if(it->contains(r)) {
				to_erase.push_back(*it);
				Range<T> tmp = *it;
				auto ret = r.getLeft();
				if(ret) {
					tmp.right(ret.value(),
							  !r.isLeftInclusive());
				}
				if(!tmp.empty()) to_insert.push_back(tmp);
				tmp = *it;
				ret = r.getRight();
				if(ret) {
					tmp.left(ret.value(),
							 !r.isRightInclusive());
				}
				if(!tmp.empty()) to_insert.push_back(tmp);
			} else if(!xa) {
				to_erase.push_back(*it);
			} else {
				if(!xb || xa.value() < xb.value()) {
					to_erase.push_back(*it);
					Range<T> tmp = *it;
					tmp.right(xa.value(),
							  !r.isLeftInclusive());
					if(!tmp.empty())
						to_insert.push_back(tmp);
				} else if(xa.value() == xb.value()
						  && r.isLeftInclusive()
						  && it->isRightInclusive()) {
					to_erase.push_back(*it);
					Range<T> tmp = *it;
					tmp.right(xb.value(), false);
					if(!tmp.empty())
						to_insert.push_back(tmp);
				}
			}
		}
		it = ranges.lower_bound(r);
		while(true) {
			if(it == ranges.end()) break;
			if(!r.contact(*it)) break;
			if(r.contains(*it))
				to_erase.push_back(*it);
			else {
				to_erase.push_back(*it);
				auto rb = r.getRight();
				if(rb) {
					Range<T> tmp = *it;
					tmp.left(rb.value(),
							 !r.isRightInclusive());
					if(!tmp.empty())
						to_insert.push_back(tmp);
				}
			}
			it++;
		}
		for(auto &e: to_erase) ranges.erase(e);
		for(auto &e: to_insert) ranges.insert(e);
	}

	optional<Range<T>> getLeft(Range<T> r) const {
		auto it = ranges.lower_bound(r);
		if(it != ranges.begin()) {
			it--;
			return *it;
		}
		return nullopt;
	}

	optional<Range<T>> getRight(Range<T> r) const {
		auto it = ranges.upper_bound(r);
		if(it != ranges.end()) {
			return *it;
		}
		return nullopt;
	}

	optional<Range<T>> get(T x) const {
		auto r = Range<T>().left(x, true).right(x, true);
		auto it = ranges.lower_bound(r);
		if(it != ranges.end()) {
			if(it->contains(r)) return *it;
		}
		if(it != ranges.begin()) {
			it--;
			if(it->contains(r)) return *it;
		}
		return nullopt;
	}

	set<Range<T>> all() const {
		return ranges;
	}

	bool contains(Range<T> r) const {
		auto it = ranges.lower_bound(r);
		if(it != ranges.end()) {
			if(it->contains(r)) return true;
		}
		if(it != ranges.begin()) {
			it--;
			if(it->contains(r)) return true;
		}
		return false;
	}

	vi getContainsRangeId(Range<T> r) const {
		vi ret;
		auto it = ranges.lower_bound(r);
		if(it != ranges.begin()) {
			it--;
			if(r.contains(*it)) ret.push_back(it->getId());
			it++;
		}
		while(true) {
			if(it == ranges.end()) break;
			if(!r.contains(*it)) break;
			ret.push_back(it->getId());
			it++;
		}
		return ret;
	}

	int getContainedRangeId(Range<T> r) const {
		auto it = ranges.lower_bound(r);
		if(it != ranges.end()) {
			if(it->contains(r)) return it->getId();
		}
		if(it != ranges.begin()) {
			it--;
			if(it->contains(r)) return it->getId();
		}
		return false;
	}

	vi getCrossRangeId(Range<T> r) const {
		vi ret;
		auto it = ranges.lower_bound(r);
		if(it != ranges.begin()) {
			it--;
			if(it->cross(r)) ret.push_back(it->getId());
			it++;
		}
		while(true) {
			if(it == ranges.end()) break;
			if(!r.cross(*it)) break;
			ret.push_back(it->getId());
			it++;
		}
		return ret;
	}

	vi getContactRangeId(Range<T> r) const {
		vi ret;
		auto it = ranges.lower_bound(r);
		if(it != ranges.begin()) {
			it--;
			if(it->contact(r)) ret.push_back(it->getId());
			it++;
		}
		while(true) {
			if(it == ranges.end()) break;
			if(!r.contact(*it)) break;
			ret.push_back(it->getId());
			it++;
		}
		return ret;
	}

	bool contains(T x) const {
		auto r = Range<T>().left(x, true).right(x, true);
		return contains(r);
	}

	vi getContainsRangeId(T x) const {
		auto r = Range<T>().left(x, true).right(x, true);
		return getContainsRangeId(r);
	}

	int getContainedRangeId(T x) const {
		auto r = Range<T>().left(x, true).right(x, true);
		return getContainedRangeId(r);
	}

	vi getCrossRangeId(T x) const {
		auto r = Range<T>().left(x, true).right(x, true);
		return getCrossRangeId(r);
	}

	vi getContactRangeId(T x) const {
		auto r = Range<T>().left(x, true).right(x, true);
		return getContactRangeId(r);
	}

	T countIntegerPoint(Range<T> r) const {
		auto it = ranges.lower_bound(r);
		T ret = 0;
		if(it != ranges.begin()) {
			it--;
			if(it->contact(r)) {
				auto R = r.intersect(*it);
				ret += R.countIntegerPoint();
			}
			it++;
		}
		while(true) {
			if(it == ranges.end()) break;
			if(!r.contact(*it)) break;
			auto R = r.intersect(*it);
			ret += R.countIntegerPoint();
			it++;
		}
		return ret;
	}

	T countMiddlePoint(Range<T> r) const {
		auto it = ranges.lower_bound(r);
		T ret = 0;
		if(it != ranges.begin()) {
			it--;
			if(it->contact(r)) {
				auto R = r.intersect(*it);
				ret += R.countMiddlePoint();
			}
			it++;
		}
		while(true) {
			if(it == ranges.end()) break;
			if(!r.contact(*it)) break;
			auto R = r.intersect(*it);
			ret += R.countMiddlePoint();
			it++;
		}
		return ret;
	}

	optional<T> mex(T x) const {
		auto R = get(x);
		if(!R) return x;
		auto ret = R.value().getRight();
		if(!ret) return nullopt;
		int ans = ret.value();
		if(R.value().isRightInclusive()) ans++;
		return ans;
	}

	bool same(T x, T y) const {
		return contains(
			Range<T>().left(x, true).right(y, true));
	}
};

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page