[출제 의도]
유명한 Largest Rectangle in a Histogram 문제(링크)에서 윗부분만이 아니라 아랫 부분의 위치도 변한다면 어떨까? 에서 시작한 문제입니다.
이 editorial은 출제 의도에 맞춰서 위 문제의 풀이를 변형하여 풀었습니다.
[문제 해설 - Largest Rectangle in a Historgam]
먼저 O(N²⁾ 해법은 어떤 위치에서 왼쪽으로 진행하면서 그 높이 이하가 되는 시작점과 오른쪽으로 진행하면서 그 높이 이하가 되는 점을 구하고, (해당 거리 * 높이)의 계산을 통해서 풀게 됩니다.
그러나 이런 문제를 O(N^2)으로 내지는 않겠죠? 저렇게 풀어서 낸다면 Time Limit Exceeded라는 결과를 받게 됩니다.
여기에서 조금 더 생각해보면 높이가 계속 높아지고 있을 때에는 왼쪽으로 이동해서 찾는 시작점이 현재 점과 같다는 것을 알 수 있습니다.
그렇다면 만약 중간에 높이가 낮아진다면 어떨까요?
중간에 높이가 낮아진다는 것은 앞의 현재 높이보다 높았던 것들의 끝점이 현재 위치라는 것을 알 수 있습니다. 또한 지금 현재 위치의 시작점은 현재 높이보다 높아지기 시작한 점이 됩니다.
이 성질을 이용해서 스택에 (시작점, 높이)를 계속 쌓으면서 높이가 낮아질 때 스택에서 빼면서 계산하고, 마지막으로 계산한 시작점을 현재 위치의 시작점으로 놓을 수 있습니다.
이렇게 푼다면 앞에서부터 한번만 쭉 보면서 풀 수 있으며, 스택에 들어가고 나오는 것도 한번씩이면 되기 때문에 O(N)의 해가 됩니다.
이를 간단히 코드로 나타낸다면 다음과 같이 됩니다.
~~~ cpp

struct in_stack
{
int pos, hi;
};
hi[n] = 0;
stack s;
for (int j = 0; j <= n; ++j)
{
in_stack c, d;
d.pos = j;
while (!s.empty())
{
c = s.top();
if (c.hi < hi[j]) break;
res >?= c.hi * (j - c.pos);
d.pos = c.pos;
s.pop();
}
d.hi = hi[j];
s.push(d);
}

[문제 해설 - Candlestick Charts]
히스토그램 문제와 다른 점은 아래 부분이 변한다는 것입니다.
따라서 모든 가능한 아래 부분의 위치(?)를 다 해본다면 O(N^2)으로  풀 수 있습니다. 아래 부분의 위치를 선택했을 때 candlestick charts가 선택된 아래 부분과 만나지 않는 경우에 주의해서 풀면 위 히스토그램 문제의 풀이를 쉽게 적용할 수 있습니다.
[spoiler="소스코드 보기"]
~~~ cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
int T;
int n, m;
int low[2001], hi[2001], lo[2001];
struct in_stack
{
        int pos, hi;
};
int main()
{
        scanf("%d", &T);
        while (T--)
        {
                scanf("%d", &n);
                for (int i = 0; i < n; ++i)
                {
                        scanf("%d%d", &low[i], &hi[i]);
                        lo[i] = low[i];
                }
                sort(lo, lo + n);
                m = unique(lo, lo + n) - lo;
                hi[n] = low[n] = -1;
                int res = 0;
                for (int i = 0; i < m; ++i)
                {
                        stack<in_stack> s;
                        for (int j = 0; j <= n; ++j)
                        {
                                in_stack c, d;
                                if (lo[i] > hi[j] || lo[i] < low[j])
                                {
                                        while (!s.empty())
                                        {
                                                c = s.top();
                                                res >?= (c.hi - lo[i]) * (j - c.pos);
                                                s.pop();
                                        }
                                        continue;
                                }
                                d.pos = j;
                                while (!s.empty())
                                {
                                        c = s.top();
                                        if (c.hi < hi[j]) break;
                                        res >?= (c.hi - lo[i]) * (j - c.pos);
                                        d.pos = c.pos;
                                        s.pop();
                                }
                                if (hi[j] <= lo[i]) continue;
                                d.hi = hi[j];
                                s.push(d);
                        }
                }
                printf("%d\n", res);
        }
}

[/spoiler]
* 이 풀이는 JM님이 의도한 풀이가 아닐거라 생각하면서 JM님의 더 개선된 알고리즘을 이용한 editorial을 기대해봅니다.