单调队列和单调栈

一.概念

目的是:维持数据结构内的一组线性数据并保证其按照单调递减或单调递增.
单调队列/栈的实现很简单,只用一个数组即可,多用于与其他算法等搭配,产生非常好的效果.

二.实现

int q[MAX],head,tail;    //队列或者栈,头,尾
void built(int &head,int &tail,int *q)    //初始化
{
    memset(q,0,sizeof(q));
    head=1,tail=0;
}
void update(int x,int &head,int &tail,int *q)    //插入数据
{
    while(tail>=head&&x ? q[tail])    //维护队列/栈的单调性
        tail--;
    q[++tail] = x;
}

三.题目

单调队列

洛谷P1886 滑动窗口

https://www.luogu.org/problemnew/show/P1886
现在有一堆数字共$N$个数字（$N<=10^6$），以及一个大小为$k$的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is $[1,3,-1,-3,5,3,6,7]$, and $k = 3$.
输入输出格式
输入格式：
输入一共有两行，第一行为$n$,$k$。
第二行为$n$个数($<MAX$).
输出格式：
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
输入样例#1：
8 3
1 3 -1 -3 5 3 6 7
输出样例#1：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
说明
50%的数据，$n<=10^5$
100%的数据，$n<=10^6$

解析

给你一组数据,和一个$k$大小的框子,框数,问框里的最大值和最小值各是多少.可以用dp做
我们可以假装有一个单调队列来装这$k$个数.然后如果保证这个队列是单增的话,那么队首这个数在这$k$个数里,一定是最小的.同理可以得到最大的数.

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#ifndef NULL
#define NULL 0
#endif
const int MAXN = 1e6 + 1;
using namespace std;

int  n, a[MAXN], q[MAXN], p[MAXN], MAX[MAXN], MIN[MAXN];
int read()
{
    int x = 0, f = 1; char c = getchar();
    while (c<'0' || c>'9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x*f;
}
int maxx(int n, int k)
{
    int head = 1, tail = 0, tot = 0;    //初始化队列
    for (int i = 1; i <= n; i++) {
        while (tail >= head && a[i] > q[tail])    //维持队列单调性
            tail--;
        q[++tail] = a[i];        //入队
        p[tail] = i;            //同时存下数的下标
        if (p[head] <= i-k)        //保证队里的数是最新的
            head++;
        if(i>=k)                //在满足往框里扔进k个数后,再取最值
            MAX[++tot] = q[head];
    }
    return tot;
}
int minn(int n, int k)
{
    int head = 1, tail = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        while (tail >= head&&a[i] < q[tail])
            tail--;
        q[++tail] = a[i];
        p[tail] = i;
        if (p[head] <= i - k)
            head++;
        if(i>=k)
            MIN[++ans] = q[head];
    }
    return ans;
}
int main()
{
    int n = read(), k = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    int tot = maxx(n, k);
    int ans = minn(n, k);
    for (int i = 1; i <= ans; i++)
        cout << MIN[i] << ' ';
    cout << '\n';
    for (int i = 1; i <= tot; i++)
        cout << MAX[i] << ' ';
    cout << '\n';
    return 0;
}

单调栈

[GXOI/GZOI2019]与或和

https://www.luogu.org/problemnew/show/P5300
题目描述
Freda 学习了位运算和矩阵以后，决定对这种简洁而优美的运算，以及蕴含深邃空间的结构进行更加深入的研究。
对于一个由非负整数构成的矩阵，她定义矩阵的AND 值为矩阵中所有数二进制AND(&) 的运算结果；定义矩阵的OR 值为矩阵中所有数二进制OR(|) 的运算结果。

给定一个N×N 的矩阵，她希望求出：

该矩阵的所有子矩阵的 AND 值之和（所有子矩阵 AND 值相加的结果）。
该矩阵的所有子矩阵的OR 值之和（所有子矩阵 OR 值相加的结果）。
接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题，所以这个问题就交给你了。

由于答案可能非常的大，你只需要输出答案对 ($10^9 + 7$)$1000000007$取模后的结果。

输入输出格式
输入格式：
输入文件的第一行是一个正整数 $N$，表示矩阵的尺寸。

接下来 $N$ 行，每行 $N$ 个自然数，代表矩阵的一行。相邻两个自然数之间由一个或多个空格隔开。

输出格式：
输出只有一行，包含两个用空格隔开的整数，第一个应为所有子矩阵 AND 值之和除以 $10^9+7$的余数，第二个应为所有子矩阵 OR 值之和除以 $10^9+7$的余数。

输入输出样例
输入样例#1：
3
1 0 0
0 0 0
0 0 0
输出样例#1：
1 9
输入样例#2：
3
1 2 3
4 5 6
7 8 9
输出样例#2：
73 314
说明
样例1解释
该 $3×3$ 矩阵共有 $9$个 $1×1$ 子矩阵、$6$ 个 $1×2$ 子矩阵、$6$ 个 $2×1$ 子矩阵、$4$ 个$2×2$ 子矩阵、$3$ 个 $1×3$ 子矩阵、$3$ 个 $3×1$ 子矩阵、$2$ 个 $2×3$ 子矩阵、$2$ 个 $3×2$ 子矩阵和 $1$ 个 $3×3$ 子矩阵。
只有一个子矩阵（仅由第一行第一列的那个元素构成的 $1×1$ 矩阵）AND 值为 $1$，其余子矩阵的AND 值均为 $0$，总和为 $1$。
包含第一行第一列那个元素的子矩阵有 $9$ 个，它们的 OR 值为 $1$，其余子矩阵的 OR 值为 $0$，总和为 $9$。
数据范围

测试点编号	$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.于是问题变为求符合条件的子矩阵的个数.
  引入一个结论:

在一个 N×M 的矩阵中，以(n,m)为右下角的子矩阵共有 N×M 个

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

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;

const int mod = 1e9 + 7;
ll ans1, ans2, n, sum;
int a[1010][1010], mx[1010];
bool b[1010][1010];

struct vec {
    int h, len;
}q[1000 + 10];

ll f1(int f)
{
    memset(mx, 0, sizeof(mx));
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        ll num = 0, tail = 0, head = 1;
        for (int j = 1; j <= n; j++) {
            mx[j] = f^(!b[i][j])?mx[j]+1:0;
            int len = 1;
            while (tail >= head && q[tail].h >= mx[j]) {
                num -= q[tail].h*q[tail].len;
                len += q[tail].len;
                tail--;
            }
            num += mx[j] * len;
            res = (res%mod + num % mod) % mod;
            tail++;
            q[tail].h = mx[j];
            q[tail].len = len;
        }
    }
    return res;
}

int main()
{
    scanf("%lld", &n);
    sum = (n*(n + 1) / 2 * n*(n + 1) / 2) % mod;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);

    for (int k = 0; k <= 31; k++) {
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++)
                if (a[i][j] & (1 << k))
                    b[i][j] = 1;
                else
                    b[i][j] = 0;
        
        ans1 = (ans1%mod + (1LL << k) % mod*f1(1) % mod) % mod;
        ans2 = (ans2%mod + (1LL << k) % mod*(sum - f1(0) + mod) % mod) % mod;
    }
    printf("%lld %lld", ans1, ans2);
}
`

POJ3250 Bad Hair Day

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

解析

维护一个单调递减的栈,比ta矮的都能看到,而进去的牛除了队尾的都会加一,所以直接ans+=tail

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>
const int INF = 0x3f3f3f3f;
const int MAX = 80000 + 10;
using namespace std;

long long p[MAX];
long long read()
{
    long long x = 0, f = 1; char c = getchar();
    while (c<'0'&&c>'9') {
        if (c == '-')    f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}
int main()
{
    int n = read(), head = 1, tail = 0;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = read();
        while (head <= tail && x >= p[tail])
            tail--;
        ans += tail;
        p[++tail] = x;
    }
    cout << ans << endl;
    return 0;
}

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

解析

私以为不如该博主讲得好:
https://www.cnblogs.com/violet-acmer/p/9780638.html#commentform

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#ifndef NULL
#define NULL 0
#endif
const int MAX = 1e6 + 1;
using namespace std;

long long  n, q[MAX], l[MAX], r[MAX], a[MAX];
long long read()
{
    int x = 0, f = 1; char c = getchar();
    while (c<'0' || c>'9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}
int main()
{
    while (n = read(), n) {
        int head = 1, tail = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = read();
            while (tail >= head&&a[i] <= a[q[tail]])        //维持单调性,注意保存的是下标
                tail--;
            l[i] = tail < head ? 1 : q[tail] + 1;        //如果它不是栈首,我们就认为它左边有矩形
            q[++tail] = i;
        }
        head =1, tail = 0;
        for (int i = n; i > 0; i--) {
            while (tail >= head&&a[i] <= a[q[tail]])
                tail--;
            r[i] = tail < head ? n : q[tail] - 1;
            q[++tail] = i;
        }
        long long res = 0;
        for (int i = 1; i <= n; i++)
            res = max(res, a[i] * (r[i] - l[i] + 1));
        cout << res << endl;
    }
    return 0;
}

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

解析

谜一样的wa点…..
左边扫一遍,右边扫一遍.
我还是不知道咋wa的

#include <cstdio>
#include <stack>
#include<iostream>
#include <algorithm>
#include <cstring>
#define MAX 100010
using namespace std;
typedef long long LL;

LL a[MAX], sum[MAX];
int le[MAX], ri[MAX],p[MAX];

int main() {
    int n;
    cin >> n;
    memset(le, -1, sizeof(le));
    memset(ri, -1, sizeof(ri));
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    int head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head<=tail && a[p[tail]] > a[i]) {
            ri[p[tail]] = i;
            tail--;
        }
        p[++tail] = i;
    }
    head = 1, tail = 0;
    for (int i = n; i >= 1; i--) {
        while (head <= tail && a[p[tail]] > a[i]) {
            le[p[tail]] = i;
            tail--;
        }
        p[++tail] = i;
    }
    LL ans = -1;
    int ans_l = -1, ans_r = -1;
    for (int i = 1; i <= n; i++) {
        int l = le[i] == -1 ? 0 : le[i],r = ri[i] == -1 ? n : ri[i] - 1;
        LL cur = (sum[r] - sum[l]) * a[i];
        if (cur > ans) {
            ans_l = l + 1;
            ans_r = r;
            ans = cur;
        }
    }
    printf("%lld\n%d %d\n", ans, ans_l, ans_r);
    return 0;
}

计蒜客 Max answer

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

解析

求区间$(l,r)*min(l,r)$,在$(l,r)$区间内取一个最小值,乘该区间内值的和,问怎样取才能取到最大值.
首先,因为数据过大,要用单调栈.
如果单套模板,会wa,因为会有负数.
故要对负数进行特判.
如果是负数…就按$o(n^2)$的算法做一遍…

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#ifndef NULL
#define NULL 0
#endif
const int MAX = 1e6 + 1;
using namespace std;

long long  n, q[MAX], l[MAX], r[MAX], a[MAX], num[MAX],maxl[MAX];
long long read()
{
    int x = 0, f = 1; char c = getchar();
    while (c<'0' || c>'9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int main()
{
    n = read();
    int head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        num[i] = num[i - 1] + a[i];
        while (tail >= head && a[i] <= a[q[tail]])
            tail--;
        l[i] = tail < head ? 1 : q[tail] + 1;
        q[++tail] = i;
    }
    head = 1, tail = 0;
    for (int i = n; i > 0; i--) {
        while (tail >= head && a[i] <= a[q[tail]])
            tail--;
        r[i] = tail < head ? n : q[tail] - 1;
        q[++tail] = i;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] < 0) {
            long long set = 0;
            for (int j = l[i]; j <= i; j++)
                maxl[i]= min(maxl[i],num[i] - num[j-1]);
            set=max(set,maxl[i]*a[i]);
            for (int j = i + 1; j <= r[i]; j++)
                set = max(set, a[i] * (maxl[i] + num[j] - num[i]));
            ans = max(ans, set);
        }
        else
            ans = max(ans, a[i] * (num[r[i]] - num[l[i] - 1]));
    cout << ans << endl;
    return 0;
}
/*
5
-8 -7 1 -7 -8
*/