标签： 单调栈

题意：有个$n\times n,n\leq 5000$的矩阵，挖掉$m,m\leq 10^6$个格子，问不包括这些格子的子矩阵个数。

做法很容易考虑：枚举一行，这一行从左往右扫，依次计算每个格子为右下角的子矩阵个数。

扫的时候维护一个单调栈，里面存(元素，以这个元素为高度的格子最长向右延伸了多少格)

为什么要存第二个项呢？我们维护的单调栈里面，每个东西实际上表示的是一个矩形，含义是：在我们处理完当前这个列后，这些矩形里的元素都可以作为合法的子矩阵左上顶点。

扫的时候维护一个东西：单调栈里所有矩形的大小和$sum$，即合法的左上顶点个数。

每次加入一个元素$x$，分以下三种情况讨论：

• $x$大于单调栈最后的元素：直接加入。长度记为1，sum加上$x$(显然多了这么多合法的格子)
• $x$等于单调栈最后的元素：单调栈最后的元素的长度加1，sum加上$x$
• $x$小于单调栈最后的元素：弹出单调栈最后的元素，并把其长度加到倒数第二个元素上，然后重复这三个check

最后我们每插入一个元素后，所维护的sum就是以这个点为右下角的答案。

另外有一个坑：输入1625 0，答案输出正确，但是从1626 0开始，答案越来越小，看起来像是溢出了，但是开-fsanitize=undefined没报任何问题，结果最后查出来了，算一行的答案时使用的是std::accumlate，初始值传的是int类型，而后累加变量自动推导为int，导致这个函数里面溢出了，然后由于ubsan并不会对包含的其他文件的代码做检查，于是挂掉了。

#include <assert.h>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using int_t = long long;
using std::cin;
using std::cout;
using std::endl;
/**
 * 1624 0 -> R
 * 1625 0 -> R
 * 1626 0 -> E 正确1749670208001 本程序 1736785306113
 * 1627 0 -> E
 */
bool block[5001][5001];
int_t upmost[5001][5001];
int_t n, m;
int main() {
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int_t i = 1; i <= m; i++) {
        int_t r, c;
        cin >> r >> c;
        block[r][c] = true;
    }
    for (int_t i = 1; i <= n; i++) {  //列
        int_t lastpos = 0;
        for (int_t j = 1; j <= n; j++) {
#ifdef DEBUG
            // cout << "block " << j << " " << i << " = " << block[j][i] <<
            // endl;
#endif
            if (block[j][i])
                lastpos = j;
            upmost[j][i] = lastpos;
#ifdef DEBUG
            cout << "upmost " << j << " " << i << " = " << upmost[j][i] << endl;
#endif
        }
    }
    int_t result = 0;
    //枚举底边行号
    for (int_t i = 1; i <= n; i++) {
        static int_t answer[5001];  // j->以(i,j)为右下角的矩形个数
        //以当前元素为右下角的矩形个数
        int_t sum = 0;
        // first为元素，second为出现次数
        std::vector<std::pair<int_t, int_t>> stack;
        stack.emplace_back(0, 0);
        for (int_t j = 1; j <= n; j++) {
            int_t x = i - upmost[i][j];  //向上延伸的空格子数(包括i,j)
            int_t count = 1;
            while (x < stack.back().first) {
                count += stack.back().second;
                sum -= stack.back().first * stack.back().second;
                stack.pop_back();
            }
            assert(sum >= 0);
            if (x == stack.back().first) {
                stack.back().second += count;
            } else {
                stack.emplace_back(x, count);
            }
            sum += x * count;
            answer[j] = sum;
            // cout << "answer col " << j << " = " << answer[j] << endl;
#ifdef DEBUG
            cout << "pushed col " << j << " val " << x << " sum = " << sum
                 << " answer = " << answer[j] << endl;
#endif
        }
        int_t currrow = std::accumulate(answer + 1, answer + 1 + n, (int_t)0);
        result += currrow;
        // cout << "answer row " << i << " = " << currrow << " " << currrow / i
        //      << " " << currrow % i << endl;
#ifdef DEBUG
        cout << "answer row " << i << " = " << currrow << endl;
#endif
    }
    cout << result << endl;
    return 0;
}

单调栈板子题..?

首先按位拆分，然后转变为统计一个01矩阵中所有全1的子矩阵（按位与）以及所有全0的子矩阵（用总矩阵数减掉即为按位或的答案）。

打表可知$n\times n$的矩阵有$(\frac{n(n+1)}2)^2$个子矩阵。

统计全1矩阵和全0矩阵本质一样，故我们先考虑统计全0矩阵。

考虑处理出来$f(i,j)$，表示如果第i行第j列的元素时0，那么往上到什么位置的元素也全都是0。对于是1的位置，$f(i,j)=-1$。

然后我们枚举一个下界$low$，表示现在我们要统计下边缘在$low$上的矩形个数。

然后从左到右扫，维护一个单调栈，单调栈内的元素是列，设$S_i$为栈中自底向上第$i$个元素，那么满足$f(low,i+1)>f(low,i)$。

先不考虑出栈，考虑入栈。

处理右下角为$(i,j)$时的答案时，设$x$表示合法的矩形数量

假设第i列的元素$i$入栈的时候，我们设$S_{-1}$表示栈内最后一个元素，$S_{-2}$以此类推。

如果加入元素i不会使得任何元素出栈，那么我们可以得到以$(i,j)$为右下角的所有合法的矩形数量为$x+f(low,i)$。

由于加入i不会导致元素出栈，故$f(low,i)$一定大于栈中其他元素的值，所以第i列较低的$S_{-1}$列可以和前面的拼起来，比$S_{-1}$高的部分可以自己成一个宽度为1的矩形。

如果导致了元素出栈呢？

左侧到$S_{-2}$，上边界到$f(low,S_{-1})$的矩形不可能再次被取到，减掉即可。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <inttypes.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;
/*
°´Î»ÌÖÂÛ
ANDֵΪ1->¾ØÕóÈ«²¿Îª1
ORֵΪ1->¾ØÕóÖÁÉÙÓÐÒ»¸ö1
ͳ¼ÆÈ«0ºÍÈ«1µÄ¾ØÕó¸öÊý£¬ÖÁÉÙÓÐÒ»¸ö1µÈ¼ÛÓÚ×Ü×Ó¾ØÕóÊý-È«0¾ØÕó¡£
*/
typedef int int_t;

using std::cin;
using std::endl;
using std::cout;
const int_t mod = 1e9 + 7;
const int_t LARGE = 1e3+3;
int_t mat[LARGE+1][LARGE+1];

//last:ij¸öλÖÃÉÏ·½µÄµÚÒ»¸ö1µÄλÖÃ
int_t count[LARGE+1][LARGE+1],last[2][LARGE+1][LARGE+1];
int_t resultAnd,resultOr;
int_t n;
int_t C2(int_t n) {
	return ((int64_t)n*(n-1)/2)%mod;
}
void countFor(int_t bit) {
	//ö¾ÙÁÐ
	for(int_t i=1; i<=n; i++) {
		last[0][0][i]=last[1][0][i]=1;
		for(int_t j=1; j<=n; j++) {
			for(int_t k=0; k<=1; k++) {
				if(count[j-1][i]!=k) {
					last[k][j][i]=j;
				} else {
					last[k][j][i]=last[k][j-1][i];
				}
				if(count[j][i]!=k) last[k][j][i]=-1;
			}
		}
	}
	int_t zero=0,one=0;
	//ö¾Ùµ×
	for(int_t low=1; low<=n; low++) {
		static int_t val[2][LARGE+1];
		for(int_t i=1; i<=n; i++) {
			for(int_t j=0; j<=1; j++) {
				if(last[j][low][i]==-1) val[j][i]=0;
				else val[j][i]=low-last[j][low][i]+1;
			}
		}
		const auto count=[&](int_t bit) {
			int_t result=0;
			int_t count = 0;
			//´Ó×óÍùÓÒɨ
			std::vector<int_t> stack;
			stack.push_back(0);
			val[bit][0]=-1;
			for(int_t i=1; i<=n; i++) {
				//ºÍÇ°ÃæÁ¬µ½Ò»ÆðµÄ & ×Ô¼ºµÄ
				count += val[bit][i];
				while(stack.size() >= 1 && val[bit][stack.back()]>=val[bit][i]) {
					count -= (stack.back() - stack[stack.size() - 2]) * (val[bit][stack.back()] - val[bit][i]);
					stack.pop_back();
				}
				stack.push_back(i);
				result += count;
			}
			return result;
		};
		zero=(zero+count(0))%mod;
		one=(one+count(1))%mod;
	}
	resultAnd=(resultAnd+(int64_t)one*(1ll<<bit)%mod)%mod;
	const auto pow2=[](int64_t x) {
		x%=mod;
		return x*x%mod;
	};
	int_t least = (pow2((int64_t)n*(n+1)/2) - zero + mod) % mod;
	resultOr=((int64_t)resultOr+least*(1ll<<bit)%mod)%mod;
}
namespace SimpleIO{
    const int_t LARGE = 5e7;
    char buf[LARGE + 1];
    char* used = buf;
    void init(){
        fread(buf,1,LARGE,stdin);
    }
    template<class T>
    void nextInt(T& x){
        x = 0;
        while(isdigit(*used) == false) used++;
        while(isdigit(*used)){
            x = x * 10 + (*used) - '0';
            used++;
        }
    }
}
int main() {
//	scanf("%d",&n);
    SimpleIO::init();
    SimpleIO::nextInt(n);
	int_t maxval=0;
	for(int_t i=1; i<=n; i++) {
		for(int_t j=1; j<=n; j++) {
//			scanf("%d",&mat[i][j]);
            SimpleIO::nextInt(mat[i][j]);
			maxval=std::max(maxval,mat[i][j]);
		}
	}
	for(int_t i=0; (1ll<<i)<=maxval; i++) {
		for(int_t j=1; j<=n; j++) {
			for(int_t k=1; k<=n; k++) {
				count[j][k]=(mat[j][k]&(1ll<<i))!=0;
			}
		}
		countFor(i);
	}
	cout << resultAnd << " " << resultOr << endl;
	return 0;
}

zz单调栈题。

刚学会单调栈zbl。

#include <iostream>
#include <utility>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1e6 + 10;
int_t height[LARGE + 1];
int_t width[LARGE + 1];
int_t left[LARGE + 1], right[LARGE + 1];
std::vector<int_t> stack;
int n;
int main() {
    scanf("%d", &n);
    for (int_t i = 1; i <= n; i++) {
        // int_t x;
        scanf("%lld", &width[i]);
        width[i] += width[i - 1];
    }
    for (int_t i = 1; i <= n; i++) {
        scanf("%lld", &height[i]);
    }
    stack.push_back(0);
    for (int_t i = 1; i <= n; i++) {
        while (height[stack.back()] >= height[i]) stack.pop_back();
        left[i] = stack.back() + 1;
        stack.push_back(i);
        // cout << "letf " << i << " = " << left[i] << endl;
    }
    stack.clear();
    stack.push_back(n + 1);
    for (int_t i = n; i >= 1; i--) {
        while (height[stack.back()] >= height[i]) stack.pop_back();
        right[i] = stack.back() - 1;
        stack.push_back(i);
    }
    int_t result = 0;
    for (int_t i = 1; i <= n; i++)
        result = std::max(result,
                          height[i] * (width[right[i]] - width[left[i] - 1]));
    cout << result << endl;
    return 0;
}