Solution

Vol9

BZOJ1113

首先注意到矩形的宽是没有意义的，于是我们可以认为矩形的宽都是一。

假设第i个矩形，在其之前具有一个矩形j，满足high(i)=high(j)且在[i,j]中没有矩形比它小，则覆盖第i个矩形是不需要额外花费的，因为我们可以用第j个矩形直接拉过去。

如果不存在，则第i个矩形显然需要额外花费。

完成上面算法的最简单手法显然是枚举（当然可以线段树优化）。

继续考察，我们发现假设出现了一个高度为i的矩形，在它之前出现过的高度大于i的都没有意义，这启示我们使用单调栈。

我们从头向尾枚举，维护一个单调栈，栈中存放的是矩形的高度，递增。每当扫描到第i个矩形，我们在单调栈中弹出所有比它高的矩形，之后检查栈顶是否和它等高，如能，则不需额外花费，否则需要额外花费，然后将它压栈。

显然，这个算法的复杂度是均摊O(n)的。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
stack<int> Q;
int da[250005];
int n;
void Solve()
{
    int ans=1;Q.push(da[1]);
    for(int i=2;i<=n;i++){
        while(!Q.empty()&&Q.top()>da[i])
            Q.pop();
        if(Q.empty()||da[i]>Q.top())
            ans++;
        Q.push(da[i]);
    }
    printf("%d\n",ans);
}
void Readdata()
{
    freopen("loli.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int crash;
        scanf("%d%d",&crash,&da[i]);
    }
}
void Close()
{
    fclose(stdin);
    fclose(stdout);
}
int main()
{
    Readdata();
    Solve();
    Close();
    return 0;
}