✅ 한 것들

---

• 백준

📝 배운 것들

---

🏷️ 세그먼트 트리

https://velog.io/@kimdukbae/자료구조-세그먼트-트리-Segment-Tree

구간을 2개로 계속 나누면서 부분합 더해놓고
나중에 필요한 부분만 꺼내쓰는 자료구조

⚔️ 백준

---

6549 히스토그램에서 가장 큰 직사각형

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

	while (true)
	{
		int count;
		cin >> count;
		if (count == 0) break;

		ll maxSize = 0;
		stack<vector<ll>> st;
		for(int i=1; i<=count+1; i++)
		{
			ll w, h, tempw, temph;
			if (i != count + 1) cin >> h;
			else h = 0;
			w = 1;
			tempw = 0;
			while (!st.empty() && st.top()[0] >= h)
			{
				temph = st.top()[0];
				tempw += st.top()[1];
				st.pop();
				maxSize = max(maxSize, temph * tempw);
			}			
			w += tempw;
			maxSize = max(maxSize, h * w);
			st.push({ h,w });
		}

		cout << maxSize << '\n';
	}
}

• 참고 풀이 : https://www.acmicpc.net/source/98497067
• 살짝 억지 부려서 이전 풀이 축소