悠然w
悠然w
全部文章
单调栈
BZOJ(6)
cdq分治(2)
CodeForces(2)
DP(6)
dsu on tree(2)
FFTNTT(4)
FWT(1)
KDtree(4)
loj(1)
luogu(6)
min-max容斥(1)
ODT/珂朵莉树(6)
OI无关(1)
二分(2)
二分图匹配(3)
克鲁斯卡尔重构树(1)
分块(1)
分治(3)
动态点分治(1)
区间DP(1)
双指针(1)
后缀自动机(1)
奇技淫巧(3)
学习笔记(4)
容斥定理(1)
差分(3)
广搜bfs(3)
扫描线(1)
数位DP(3)
数论(1)
整体二分(1)
文化课(1)
最小生成树(1)
最短路(3)
未归档(57)
杂记(11)
树状数组(4)
树链剖分(1)
概率&期望(3)
模拟(4)
洛谷(10)
状压DP(3)
生成函数(2)
矩阵乘法&矩阵快速幂(2)
矩阵乘法&矩阵快速幂(2)
矩阵树定理(2)
线段树(4)
组合数学(1)
结论题(2)
考试总结(20)
莫队(1)
贪心(3)
随机(2)
题解(1)
高斯消元(2)
高精度(6)
归档
标签
去牛客网
登录
/
注册
悠然w的博客
全部文章
/ 单调栈
(共8篇)
牛客OI月赛12-提高组 区间异或和异或区间最大值异或区间最小值 题解
单调栈&可持久化0/1trie树 题目链接 题目描述 小w学会了RMQ算法,他现在可以求出一个给定数组某一段子区间的最大值,最小值。 在这之前,他也学会了前缀和,并且他知道前缀和可以扩展到位运算求出区间异或和。 现在你给了他一个长度大小为n的数组,为了考察小w写RMQ以及前缀异或和的正...
2019-10-12
0
1091
牛客OI月赛12-提高组 区间异或和异或区间最大值异或区间最小值 题解
单调栈&可持久化0/1trie树 题目链接 题目描述 小w学会了RMQ算法,他现在可以求出一个给定数组某一段子区间的最大值,最小值。 在这之前,他也学会了前缀和,并且他知道前缀和可以扩展到位运算求出区间异或和。 现在你给了他一个长度大小为n的数组,为了考察小w写RMQ以及前缀异或和的正...
2019-10-12
0
0
AT2060 【Minimum Sum】
单调栈 这是某次olinr巨佬给我们出的考试题。首先暴力\(O(n^2)\)是不能过的(废话),我们考虑每一个数值对答案的贡献,也就是ta能当最小值的序列个数。 倘若ta能成为最小值,那么也就是在这个数列里没有比ta大的数值,这也就转化为了求出右边第一个比ta小的值的位置和左边第一个比ta小的值...
2019-09-25
0
364
AT2060 【Minimum Sum】
单调栈 这是某次olinr巨佬给我们出的考试题。首先暴力\(O(n^2)\)是不能过的(废话),我们考虑每一个数值对答案的贡献,也就是ta能当最小值的序列个数。 倘若ta能成为最小值,那么也就是在这个数列里没有比ta大的数值,这也就转化为了求出右边第一个比ta小的值的位置和左边第一个比ta小的值...
2019-09-25
0
0
AT2060 【Minimum Sum】
单调栈 这是某次olinr巨佬给我们出的考试题。首先暴力\(O(n^2)\)是不能过的(废话),我们考虑每一个数值对答案的贡献,也就是ta能当最小值的序列个数。 倘若ta能成为最小值,那么也就是在这个数列里没有比ta大的数值,这也就转化为了求出右边第一个比ta小的值的位置和左边第一个比ta小的值...
2019-09-25
0
398
Luogu P2659 美丽的序列
单调栈 只是一个比较简单的单调栈题目。我们换一种思考方式,我们枚举每段数列的最小值,然后我们发现当ta所能成为最小值的范围越大,对最终的答案的贡献也就越大。所以我们考虑求出ta所能成为最小值的数列的范围。 这也就转化为了求出右边第一个比ta小的值的位置和左边第一个比ta小的值的位置的问题。这可以...
2019-09-25
0
423
Luogu P2659 美丽的序列
单调栈 只是一个比较简单的单调栈题目。我们换一种思考方式,我们枚举每段数列的最小值,然后我们发现当ta所能成为最小值的范围越大,对最终的答案的贡献也就越大。所以我们考虑求出ta所能成为最小值的数列的范围。 这也就转化为了求出右边第一个比ta小的值的位置和左边第一个比ta小的值的位置的问题。这可以...
2019-09-25
0
0
Luogu P2659 美丽的序列
单调栈 只是一个比较简单的单调栈题目。我们换一种思考方式,我们枚举每段数列的最小值,然后我们发现当ta所能成为最小值的范围越大,对最终的答案的贡献也就越大。所以我们考虑求出ta所能成为最小值的数列的范围。 这也就转化为了求出右边第一个比ta小的值的位置和左边第一个比ta小的值的位置的问题。这可以...
2019-09-25
0
323