单调栈 – Tgotp-Blog

2096: [Poi2010]Pilots

维护两个单调栈随便搞搞就好了。

c++代码如下:

 

3238: [Ahoi2013]差异

辣鸡错误毁我时间。。。

ac与wa的区别。。。

用sa求出height即可,答案即为所有子区间最小值 之和,维护一个单调递增的单调栈。

c++代码如下:

 

1113: [Poi2008]海报PLA

我是个奇葩。。。这题都能想半天。。。

观察发现如果一个矩形能被省掉,那么前面比他高的所有情况中一定有一个和他相同的。。。

维护一个单调栈,最后比较一下top是否与当前值相同,相同的话此块可被前面覆盖,ans--。

c++代码如下:
[crayon-5ad87b1f8ecdb224[......]

Read more