单调队列和单调栈 | Kyons'Blog

## 三.题目

### 单调队列

#### 洛谷P1886 滑动窗口

https://www.luogu.org/problemnew/show/P1886

The array is $[1,3,-1,-3,5,3,6,7]$, and $k = 3$.

8 3
1 3 -1 -3 5 3 6 7

-1 -3 -3 -3 3 3
3 3 5 5 6 7

50%的数据，$n<=10^5$
100%的数据，$n<=10^6$

### 单调栈

#### [GXOI/GZOI2019]与或和

https://www.luogu.org/problemnew/show/P5300

Freda 学习了位运算和矩阵以后，决定对这种简洁而优美的运算，以及蕴含深邃空间的结构进行更加深入的研究。

3
1 0 0
0 0 0
0 0 0

1 9

3
1 2 3
4 5 6
7 8 9

73 314

 测试点编号 $n$ 的规模 矩阵中的自然数 $10$ $1≤n≤1000$ $≤2^{31} - 1$

#### 解析

1.对于两个数a,b进行位运算,每一位的位运算是单独的.所以我们可以按照位将整个矩阵分层为多个0,1矩阵.每一位的0,1矩阵的位运算和按二进制的方式加起来,便是a,b的矩阵位运算和.
2.于是,题目变成只有0,1两个数的问题.
对于位运算和,只有当一个子矩阵中所有数为1时,该子矩阵的&和为1,否则为0,也就是说,我们求一个矩阵中子矩阵的&和的和,只需要统计共有多少个全是1的矩阵即可.
当一个子矩阵中的所有数为0时,该子矩阵的|和为0.当我们求一个矩阵中子矩阵的|和,只需要在总|和中减去全为0的矩阵个数即可.
3.于是问题变为求符合条件的子矩阵的个数.
引入一个结论:

4.所以答案就变成了,以(n,m)为右下角的符合条件的子矩阵有多少个.
那么,如何得到以(n,m)为右下角的子矩阵最大的个数呢?
我们转换一下思维,问题便可以变为:在i-th处以高为h-i的矩阵向左的最大扩展长度为多少.也就是单调栈.
于是问题就解决啦

Description
Some of Farmer John’s N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.
Each cow i has a specified height hi (1 ≤ $h_i$ ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.
Consider this example:

        =
=       =
=   -   =         Cows facing right -->
=   =   =
= - = = =
= = = = = =
1 2 3 4 5 6 

Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow’s hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow’s hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!
Let ci denote the number of cows whose hairstyle is visible from cow i; please compute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.
Input
Line 1: The number of cows, N.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i.
Output

Line 1: A single integer that is the sum of c1 through cN.
Sample Input
6
10
3
7
4
12
2
Sample Output
5
Source
USACO 2006 November Silver

#### POJ 2559 Largest Rectangle in a Histogram

Description
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.
Input
The 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<=$h_i$<=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.
Output
For 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.
Sample Input
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0
Sample Output
8
4000
Hint
Huge input, scanf is recommended.
Source
Ulm Local 2003

#### POJ2796 Feel Good

Description
Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people’s memories about some period of life.
A new idea Bill has recently developed assigns a non-negative integer value to each day of human life.
Bill calls this value the emotional value of the day. The greater the emotional value is, the better the daywas. Bill suggests that the value of some period of human life is proportional to the sum of the emotional values of the days in the given period, multiplied by the smallest emotional value of the day in it. This schema reflects that good on average period can be greatly spoiled by one very bad day.
Now Bill is planning to investigate his own life and find the period of his life that had the greatest value. Help him to do so.
Input
The first line of the input contains n - the number of days of Bill’s life he is planning to investigate(1 <= n <= 100000). The rest of the file contains n integer numbers a1, a2, … an ranging from 0 to 106 - the emotional values of the days. Numbers are separated by spaces and/or line breaks.
Output
Print the greatest value of some period of Bill’s life in the first line. And on the second line print two numbers l and r such that the period from $l_{th}$ to $r_{th}$ day of Bill’s life(inclusive) has the greatest possible value. If there are multiple periods with the greatest possible value,then print any one of them.
Sample Input
6
3 1 6 4 5 2
Sample Output
60
3 5
Source
Northeastern Europe 2005

#### 解析

https://nanti.jisuanke.com/t/38228
Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.
Now she is planning to find the max value of the intervals in her array. Can you help her?

##### Input

First line contains an integer $n$($1≤n≤5×10^5$).
Second line contains nn integers represent the array $a(−10 ^5 ≤a_i ≤10^5)$.

##### Output

One line contains an integer represent the answer of the array.

5
1 2 3 4 5

36

#### 解析

//删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载