有关单调栈优化的相关例题

前言

因为最近很多单调栈优化的多校题没做出来qwq，为了更好的理解，所以今晚做了几个例题来稍微掌握单调栈的套路，顺便觉得要养好习惯理清思路就写写笔记啥的……（事实上这个是我做题遇到的一个子问题，但发现是个非常非常典的东西，补完这个我就继续去做莫比乌斯那题去啦~~）

典1

给定一个 $n×m$的$01$矩阵，求全是$1$的子矩阵个数。

比较优秀的暴力

预处理每个$f_{i,j}$表示这个位置能向左扩展的数量

如：

100000

011010

111100

111000

$f$数组为：

100000

012010

123400

123000

枚举$f_{ij}$时，对于每一个我们可以计算——以$i$为子矩阵下界，$j$为子矩阵右界，子矩阵往左不会超过$f_{ij}$长度的方案数。

我们往上枚举，对当前子矩阵最多能取的宽度记作$len$，由于会遇到宽度越来越”窄“的$f_{xj} \ \ (x\le i-1)$，很明显$len$会不断变小，每次枚举，我们的答案就会加上$len$

对于每一个下标的方案数计算，我们都是 $O(n)$，总复杂度$O(n^3)$

正解

我们从上面的枚举过程可以发现，就算上面有比较长的宽度，也会被后面比较窄的给约束，我们试图只存往上越来越窄的 ，每个比较长的答案都直接算进那个比较窄的答案里面，我们发现这样还是不行，要枚举栈的每一个元素里的答案，不妨我们同时处理一下栈里面答案的前缀和，这样便只需要得到栈顶的答案即可。

具体过程如下

也就是，每次来一个新的数，弹出上面所有>=自己宽度的数，统计弹出了多少数量$num$,则当前枚举下的答案$ans$加上$(num+1)\times f_{ij}$ ，此时栈顶也就是第一个比自己窄的元素，直接$ans$加上栈顶的答案。然后再往栈里入栈一个类似$pair(f_{ij},ans)$的东西

时间复杂度$O(n^2)$

扩展典2：求最大全1矩阵

同理先计算出上面的$f_{ij}$

对于每个下标，都用单调栈预处理出①上面比它小的第一个下标是什么②下面比它小的第一个下标是什么，然后计算即可

例题：City Game

代码模板

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const double eps=1e-8;
const int INF=0x3f3f3f3f,mod=998244353;

#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif

const int N=1003;
int minup[N];//第一个比自己fij小的下标是什么
int mindn[N];
int a[N][N];
int f[N][N];
int n,m;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                char _[2];
                scanf("%s",_);
                if(_[0]=='R') a[i][j]=0;
                else a[i][j]=1;

                if(a[i][j]==1) f[i][j]=f[i][j-1]+1;
                else f[i][j]=0;
            }
        }

        int res=0;
        for(int j=1;j<=m;j++)
        {
            vector<int> stk(n+3);
            int top=0;

            for(int i=1;i<=n;i++)
            {
                while(top&&f[stk[top]][j]>=f[i][j]) top--;

                minup[i]=stk[top];
                stk[++top]=i;
            }

            top=0;
            stk[0]=n+1;
            for(int i=n;i>=1;i--)
            {
                while(top&&f[stk[top]][j]>=f[i][j]) top--;

                mindn[i]=stk[top];
                stk[++top]=i;
            }

            for(int i=1;i<=n;i++)
            {
                int ans=(mindn[i]-minup[i]-1)*f[i][j];
                res=max(res,ans);
            }
        }
        printf("%d\n",res*3);
    }
}

小例题qwq

GXOI/GZOI2019]与或和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

[GXOI/GZOI2019]与或和

题目描述

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

对于一个由非负整数构成的矩阵，她定义矩阵的 $\texttt{AND}$ 值为矩阵中所有数二进制 $\texttt{AND(\&)}$ 的运算结果；定义矩阵的 $\texttt{OR}$ 值为矩阵中所有数二进制 $\texttt{OR(|)}$ 的运算结果。

给定一个 $N \times N$ 的矩阵，她希望求出：

1. 该矩阵的所有子矩阵的 $\texttt{AND}$ 值之和（所有子矩阵 $\texttt{AND}$ 值相加的结果）。
2. 该矩阵的所有子矩阵的 $\texttt{OR}$ 值之和（所有子矩阵 $\texttt{OR}$ 值相加的结果）。

接下来的剧情你应该已经猜到——Freda 并不想花费时间解决如此简单的问题，所以这个问题就交给你了。

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

3
1 0 0
0 0 0
0 0 0

样例输出 #1

1 9

样例 #2

样例输入 #2

3
1 2 3
4 5 6
7 8 9

样例输出 #2

73 314

提示

样例1解释

该 $3 \times 3$ 矩阵共有 $9$ 个 $1 \times 1$ 子矩阵、$6$ 个 $1 \times 2$ 子矩阵、$6$ 个 $2 \times 1$ 子矩阵、$4$ 个 $2 \times 2$ 子矩阵、3 个 $1 \times 3$ 子矩阵、$3$ 个 $3 \times 1$ 子矩阵、$2$ 个 $2 \times 3$ 子矩阵、$2$ 个 $3 \times 2$ 子矩阵和 $1$ 个 $3 \times 3$ 子矩阵。
只有一个子矩阵（仅由第一行第一列的那个元素构成的 $1 \times 1$ 矩阵）$\texttt{AND}$ 值为 $1$，其余子矩阵的 $\texttt{AND}$ 值均为 $0$，总和为 $1$。
包含第一行第一列那个元素的子矩阵有 $9$ 个，它们的 $\texttt{OR}$ 值为 $1$，其余子矩阵的 $\texttt{OR}$ 值为 $0$，总和为 $9$。

数据范围

另外有一组不计分的 hack 数据，放在 subtask 1 中，数据范围与测试点 $6 \sim 10$ 一致。

题解

对于AND：

对于每一个进制位单独算：

不妨有：

000011

001111

000111 ※

011111

和前面同理，>=当前的就弹出

$当前的答案当前的答案=len\times (num+1)+stk[top].second$ //$num$即弹出了的数量

对于OR：

我们考虑容斥：

对于每一个进制位：值为$(所有子矩阵的数量-子矩阵的当前二进制位均为0的数量)\times 2^{w}$

①先算出$n\times m$的矩阵的子矩阵数量：$\sum_{i=1}^n\sum_{j=1}^nij=(\frac{(1+n)\times n}{2})^2$

②减去每一个二进制位为0的子矩阵数量即可

模板代码

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
// #define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const double eps=1e-8;
const int INF=0x3f3f3f3f,mod=1e9+7;

#ifndef ONLINE_JUDGE
#define debug(...)
#include<debug>
#else
#define debug(...)
#endif

const int N=1003;
int a[N][N];
int f[N][N];
int n;
struct lwy
{
    int id;
    int num;//当前弹出的数量
    int ans;//预处理的前缀和值
};
ll squ(ll x)
{
    x%=mod;
    return x*x%mod;
}
int matirx_num(int w,int ty)//a[i][j]>>w&1是否为ty
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((a[i][j]>>w&1)==ty) f[i][j]=f[i][j-1]+1;
            else f[i][j]=0;

    ll res=0;
    for(int j=1;j<=n;j++)//对于每一列都要做
    {
        vector<lwy> stk(n+3);
        int top=0;
        for(int i=1;i<=n;i++)//枚举每一行
        {
            int num=1;
            while(top&&f[stk[top].id][j]>=f[i][j])
            {
                num+=stk[top].num;
                top--;
            }

            int ans=(1ll*num*f[i][j]+stk[top].ans)%mod;
            res=(res+ans)%mod;
            top++;
            stk[top].id=i;
            stk[top].num=num;
            stk[top].ans=ans;
        }
    }

    return res;
}
int main()
{
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);

    ll res1=0;
    for(int w=0;w<31;w++)
    {
        int ans=1ll*matirx_num(w,1)*(1<<w)%mod;
        res1=(res1+ans)%mod;
    }

    ll res2=squ(1ll*(1+n)*n/2)*(2147483647%mod)%mod;
    for(int w=0;w<31;w++)
    {
        int ans=1ll*matirx_num(w,0)*(1<<w)%mod;
        res2=(res2-ans)%mod;
    }
    res2=(res2+mod)%mod;

    printf("%lld %lld\n",res1,res2);
}