Segment Set(区間をsetで管理するやつ) (structure/segment_set.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-11-27 01:18:20+09:00

なにこれ

区間の集合についてのクエリを処理する構造体

コンストラクタ

• SegmentSet()：初期化した集合 $S$ を得る．

メンバ関数

• insert(x)：$S \leftarrow S \cup \{x\}$
• insert(l, r)：$S \leftarrow S \cup \{l, l+1, …, r-1, r\}$
• erase(x)：$S \leftarrow S \setminus \{x\}$

• erase(l, r)：$S \leftarrow S \setminus \{l, l+1, …, r-1, r\}$

• get_seg(x)：$x$ が所属する区間の両端の値をもつ pair を返す．$x$ がどの区間にも所属しない場合は pair(0, -1) を返す．
• min()：最も左にある区間の左端の値を返す．
• max()：最も右にある区間の右端の値を返す．
• mex(x)：$x$ 以上であって集合に含まれない値のうち最小のものを返す．
• same(x, y)：$x$ と $y$ が同じ区間に含まれる場合は true，そうでない場合は false を返す．
• size()：区間の数を返す．
• out()：区間の一覧表示を出力する．

計算量

区間の数を $n$ とする．

• insert(x)：$O(\log n)$
• insert(l, r)：$O(\log n)$
• erase(x)：$O(\log n)$

• erase(l, r)：$O(\log n)$

• get_seg(x)：$O(\log n)$
• min()：$O(1)$
• max()：$O(1)$
• mex(x)：$O(\log n)$
• same(x, y)：$O(\log n)$
• size()：$O(1)$
• out()：$O(n)$

参考

• 要素の追加・削除と mex を対数時間で処理するよ - えびちゃんの日記
• 区間をsetで管理するやつ - satanic0258.github.io

Verified with

• test/aoj_2880.cpp
• test/yuki_0674.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> struct SegmentSet {
private:
	map<T, T> mp;

public:
	SegmentSet() : mp(){};

	void insert(T x) {
		insert(x, x);
	}
	void insert(T l, T r) {
		assert(l <= r);
		auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r + 1);
		if(itr_l != mp.begin()) {
			if((--itr_l)->second < l - 1) itr_l++;
		}

		if(itr_l != itr_r) {
			l = std::min(l, itr_l->first);
			r = std::max(r, prev(itr_r)->second);
			mp.erase(itr_l, itr_r);
		}

		mp[l] = r;
	}

	void erase(T x) {
		erase(x, x);
	}
	void erase(T l, T r) {
		assert(l <= r);
		auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r);
		if(itr_l != mp.begin()) {
			if((--itr_l)->second < l) itr_l++;
		}

		if(itr_l == itr_r) return;

		T tmp_l = itr_l->first, tmp_r = prev(itr_r)->second;
		mp.erase(itr_l, itr_r);
		if(tmp_l < l) mp[tmp_l] = l - 1;
		if(r < tmp_r) mp[r + 1] = tmp_r;
	}

	pair<T, T> get_seg(T x) {
		auto itr = mp.upper_bound(x);
		if(itr == mp.begin() or (--itr)->second < x) return pair<T, T>(0, -1);
		return pair<T, T>(itr->first, itr->second);
	}

	T min() {
		return mp.begin()->first;
	}

	T max() {
		return mp.rbegin()->second;
	}

	T mex(T x = 0) {
		pair<T, T> p = get_seg(x);
		if(p.first > p.second) return x;
		return p.second + 1;
	}

	bool same(T x, T y) {
		pair<T, T> p = get_seg(x);
		return p.first <= p.second and p.first <= y and y <= p.second;
	}

	int size() {
		return int(mp.size());
	}

	void out() {
		for(auto [l, r] : mp) cout << "[" << l << ", " << r << "]\n";
	}
};

#line 2 "structure/segment_set.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> struct SegmentSet {
private:
	map<T, T> mp;

public:
	SegmentSet() : mp(){};

	void insert(T x) {
		insert(x, x);
	}
	void insert(T l, T r) {
		assert(l <= r);
		auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r + 1);
		if(itr_l != mp.begin()) {
			if((--itr_l)->second < l - 1) itr_l++;
		}

		if(itr_l != itr_r) {
			l = std::min(l, itr_l->first);
			r = std::max(r, prev(itr_r)->second);
			mp.erase(itr_l, itr_r);
		}

		mp[l] = r;
	}

	void erase(T x) {
		erase(x, x);
	}
	void erase(T l, T r) {
		assert(l <= r);
		auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r);
		if(itr_l != mp.begin()) {
			if((--itr_l)->second < l) itr_l++;
		}

		if(itr_l == itr_r) return;

		T tmp_l = itr_l->first, tmp_r = prev(itr_r)->second;
		mp.erase(itr_l, itr_r);
		if(tmp_l < l) mp[tmp_l] = l - 1;
		if(r < tmp_r) mp[r + 1] = tmp_r;
	}

	pair<T, T> get_seg(T x) {
		auto itr = mp.upper_bound(x);
		if(itr == mp.begin() or (--itr)->second < x) return pair<T, T>(0, -1);
		return pair<T, T>(itr->first, itr->second);
	}

	T min() {
		return mp.begin()->first;
	}

	T max() {
		return mp.rbegin()->second;
	}

	T mex(T x = 0) {
		pair<T, T> p = get_seg(x);
		if(p.first > p.second) return x;
		return p.second + 1;
	}

	bool same(T x, T y) {
		pair<T, T> p = get_seg(x);
		return p.first <= p.second and p.first <= y and y <= p.second;
	}

	int size() {
		return int(mp.size());
	}

	void out() {
		for(auto [l, r] : mp) cout << "[" << l << ", " << r << "]\n";
	}
};

Back to top page