Category Archives: 单调栈

HDU 5749 Colmerauer (乱搞)

Peter有一个n×m的矩阵M. 定义S(a,b)为M的所有大小为a×b的子矩阵的权值和. 一个矩阵的权值是这 …

CSU A Simple Problem (单调队列)

给出n个数字, 求一段最长的连续区间, 使得区间最大值-最小值不超过k. 题目链接: here 用l, r维护 …

POJ 3415 Common Substrings (后缀数组,单调栈优化)

给出两个串,定义f(i, j, k)表示A[i…..i + k – 1] = B[j& …

Codeforces 548D Mike and Feet (单调栈)

题意:给出n个数,然后定义xi为长度是i的区间的最小值,然后计算所有长度相同的区间最小值的最大值. 题解:直接 …

XTU 1205 Range (单调栈)

题意:求出所有子区间最大值最小值差+1的和。 题解:问题等价于:计算单个数作为一个区间的最大值或者最小值的贡献 …

FZU 2190 非提的救赎 (单调栈)

题目意思就求给定矩阵中包含w字符串的子子矩阵个数。 如果直接暴力是O(n^3),但是我们会发现求某个字矩阵的过 …

poj 2082 Terrible Sets (单调栈)

给出n个长方形排成一列,各自有各自的w、h,现在要求这些长方形组成的矩形的最大面积。 这列抽闲成的问题就是:求 …