【STL-MAP】NYOJ 991 Registration system

A new e-mail service “Berlandesk” is going to be opened in Berland in the near future. The site administration wants to launch their project as soon as possible, that’s why they ask you to help. You’re suggested to implement the prototype of site registration system. The system should work on the following principle. 继续阅读【STL-MAP】NYOJ 991 Registration system

SDAU训练日志第57篇(2019年2月10日)

今天肝了八个题,其中有一两个思路不是很明确,看了一下题解的思路又写的,另外,严格不严格的单调的符号弄错了好几次,靠单步调试才找出来错误ORZ,心态爆炸。
单调栈/队列真是个好东西,就是怕比赛的时候看到了能用的题却想不到,今天因为是单调专题啥题都往单调栈/队列上想,有了方向自然不难。
此外L和M题感觉在逗我??求最大值也能过?数据也太水了吧。。
还有几个题。。在AC和TLE的边缘来回试探。。
我这碰见题就想上暴力的坏习惯要改了。。。
暴力一时爽,一直暴力一直爽

【单调栈】Largest Rectangle in a 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 on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles: 
 
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.

InputThe input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1 <= n <= 100000. Then follow n integers h1, …, hn, where 0 <= hi <= 1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.OutputFor each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line. 继续阅读【单调栈】Largest Rectangle in a Histogram