Boj 2243) 사탕상자

문제

백준 2243

설명

세그먼트 트리를 간단히 응용하면 되는 문제임.

• 사탕의 갯수의 누적합으로 세그먼트 트리를 운영함.
• 처음으로 원하는 사탕의 순서보다 누적합이 같거나 큰 노드의 위치를 찾으면 됨.

삽질기록

이 문제에서 삽질하기 좋은 부분이 하나 있는데, 사탕을 뽑는 경우 사탕이 맛있는 순위 -> 그 사탕의 맛등급 변환을 해놓고 사탕이 맛있는 순위 의 사탕을 지우는 경우가 있음.

자신이 구한 사탕의 맛등급을 빼야 하는 거임

시간 복잡도

O(N*Log(N))

코드

template<typename T, size_t _Size>
class SegmentTree
{
	template<typename F>
	struct Node {
		Node() : v(0) {}
		Node(F v) : v(v) {}
		Node operator+(const Node& in) { return v + in.v; }
		F v = 0;
	};
public:
	void Init(int s, int e) { _s = s; _e = e; }
	void Update(int i, function<T(T)> op) { _t1 = i; this->op = op; Update_Recursive(1, _s, _e); }
	int Query(T x) { return Query_Recursive(x, 1, _s, _e); }

private:
	void Update_Recursive(int x, int s, int e)
	{
		if (s == e && s == _t1) { nodes[x] = op(nodes[x].v); return; }
		int m = (s + e) / 2;
		if (_t1 <= m) Update_Recursive(2 * x, s, m);
		else Update_Recursive(2 * x + 1, m + 1, e);
		nodes[x] = nodes[2 * x] + nodes[2 * x + 1];
	}

	int Query_Recursive(T v, int x, int s, int e)
	{
		int m = (s + e) / 2;
		T left = nodes[x * 2].v;
		if(v <= left) return Query_Recursive(v, x * 2, s, m);
		else if(v - left <= nodes[x*2+1].v) return Query_Recursive(v - left, x * 2 + 1, m + 1, e);
		return e;
	}

private:
	Node<T> nodes[_Size * 4];
	int _s, _e, _t1, _t2;
	function<T(T)> op;
};

SegmentTree<int, 1048576> seg;

int main()
{
	fastio;

	int n;
	int t1, t2, t3;
	seg.Init(1, 1000000);
	
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> t1;
		if (t1 == 1) 
		{
			cin >> t2;   // t2 번째 애를 뽑음
			t3 = seg.Query(t2);
			cout << t3 << '\n';
			seg.Update(t3, [](int a) {return a - 1; });
		}
		else {
			cin >> t2 >> t3;   // t2 의 맛을 t3 개 넣음
			seg.Update(t2, [t3](int a) { return a + t3; });
		}
	}
}