XJOI 3606 最大子矩形面積/LightOJ 1083 Histogram（單調棧/笛卡爾樹）

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3 measured in units where the width of the rectangles is 1.

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case contains a line with an integer N (1 ≤ N ≤ 30000) denoting the number of rectangles. The next line contains Nspace separated positive integers (≤ 30000) denoting the heights.

Output

For each case, print the case number and the largest rectangle that can be made.

Sample Input

2

7

2 1 4 5 1 3 3

5

4 4 3 2 4

Sample Output

Case 1: 8

Case 2: 10

題意：有一系列的長條狀的矩形，寬度都為1，相鄰的豎立在x軸上，求最大的子矩形

胡扯：

有一回對我說道，“你學過算法麼？”我略略點一點頭。他說，“學過算法，……我便考你一考。XJOI的最大子矩形面積，怎樣寫的？”我想，AKIOI的人，怎麼也來考我？便回過臉去，不再理會。孔乙己等了許久，很懇切的說道，“不能寫罷？……我教給你，記着！這些算法應該記着。将來AKIOI的時候，秒題要用。”我暗想我和IOI的等級還很遠呢，而且IOI也從不将這種題搬去；又好笑，又不耐煩，懶懶的答他道，“誰要你教，不是用單調棧胡搞毛搞麼？”孔乙己顯出極高興的樣子，将兩個指頭的長指甲敲着鍵盤，點頭說，“對呀對呀！……最大子矩形面積有四樣寫法，你知道麼？”我愈不耐煩了，努着嘴走遠。孔乙己剛打開了c++，想在上面寫代碼，見我毫不熱心，便又歎一口氣，顯出極惋惜的樣子。

題解：

這題的确有四種解法

單調棧、笛卡爾樹、類似kmp的解法、一種st表

嗯，後面兩種我連名字都說不準确，是以還是不講了

主要寫兩種常用的解法

首先是單調棧

單調棧就是一種棧内單調的資料結構，至于怎麼維護，比如說一個單調遞增的單調棧，你隻需要在每加入一個數的時候，把所有比目前數大的棧頂全部彈掉就可以了

如果一個數被彈掉了，說明他能控制的矩形也已經到頭了，是以就可以統計答案了，答案就是高度乘以(出去時間-進入時間)

然後唯一要注意的是該數的進入時間是第一個比他小的數的進入時間+1（他在棧中時下面的元素），而不是i，如果直接減的話就用進入時間就可以了

代碼如下：

#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct node
{
    int time,val;
};
int n,a[100010],b[100010];
stack<node> s;
long long ans;

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1; i<=n; i++)
    {
        int w=i;
        while((!s.empty())&&s.top().val>a[i])
        {
            int ti=s.top().time;
            w=ti;
            int v=s.top().val;
            ans=max(ans,1ll*(i-ti)*v);
            s.pop();
        }
        s.push((node){w,a[i]});
    }
    while(!s.empty())
    {
        int ti=s.top().time;
        int v=s.top().val;
        ans=max(ans,1ll*(n-ti+1)*v);
        s.pop();
    }
    printf("%lld\n",ans);
}      

然後是笛卡爾樹

笛卡爾樹的中序周遊就是原序列（二叉搜尋樹性質），而他的每個節點的值都保證是其子樹中的極值（堆性質）

笛卡爾樹是可以O（n）建構的

将點i先扔到i-1的兒子下，然後比較i-1的所有祖先，一直找到第一個值比a[i]小的祖先，把這顆祖先的右兒子改成他，把原來的右兒子改成他的左兒子

均攤分析複雜度是O（n）

建出了樹可以直接用size*tr[i].num來算出最大子矩形面積

不過我是直接記錄每個點的pos然後瞎搞的

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

struct node
{
    int fa,ls,rs,num,pos;
}tr[100010];
int a[100010],n;
long long ans;

void dfs(int pos,int l,int r)
{
    if(l>r) return ;
    ans=max(ans,1ll*(r-l+1)*a[pos]);
    dfs(tr[pos].ls,l,tr[pos].pos-1);
    dfs(tr[pos].rs,tr[pos].pos+1,r);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }    
    tr[0].num=0;
    tr[0].rs=1;
    tr[1].num=a[1];
    tr[1].pos=1;
    for(int i=2;i<=n;i++)
    {
        tr[i].num=a[i];
        tr[i].pos=i;
        int p;
        for(p=i-1;tr[i].num<tr[p].num;p=tr[p].fa);
        tr[i].ls=tr[p].rs;
        tr[p].rs=i;
        tr[i].fa=p;
    }
    dfs(tr[0].rs,1,n);
    printf("%lld\n",ans);
}