单调数据结构

题目定义一个下标 是序列 的后缀最大值下标当且仅当对于所有的 ≤|| 都有 。其中 || 表示序列 的长度。给出整数 和一个长为 的序列 对于每个 1≤≤ 输出 1∼ 所有后缀最大值下标的异或和。思路考虑用一个栈来维护当前 1∼ 所有的后缀最大值下标容易发现栈中的数单调递增指栈顶到栈底的下标对应的值单调递增。当遍历到 时如果栈顶存放的下标 满足 则因为栈是单调递增的栈中的其他下标对应的值均大于 可以正确维护。如果不满足条件则需要不断弹出栈顶直到满足条件。并将 入栈栈中的下标即为后缀最大值下标Code:vectorint stk; int ans0; for(int i1;in;i){ while(!stk.empty()a[stk.back()]a[i]){ ans^stk.back(); stk.pop_back(); } stk.push_back(i); coutans ; }复杂度共有 次循环且共执行了 次入栈操作时间复杂度 ()。单调栈需要额外空间空间复杂度 () 。单调队列题目将单调栈的问题稍加变化给出整数 , 和一个长为 的序列 对于每个长度为 的区间输出该区间内所有后缀最大值下标的数量。思路这个问题对比上个问题来说多了一个删除过期元素的功能。可以用 STL 中的 deque 双端队列来维护。每次循环开始时先从队首front取出过期元素。再按照单调栈的方法维护单调队列还可以求区间最小/最大值将新的下标加入队列中后队首的下标就是最值所在的下标Codedequeint q; int ans0; for(int i1;in;i){ while(!q.empty()q.front()i-k){ ans--; q.pop_front(); } while(!q.empty()a[q.back()]a[i]){ ans--; q.pop_back(); } q.push_back(i); ans; if(ik)coutans ; }复杂度时间复杂度 ()空间复杂度 ()例题P6510 奶牛排队题意给定一个长度为 的序列 求出满足区间内 最小且 最大的区间 [,] 的最大长度。 2≤≤105 思路考虑暴力枚举右端点 对每个 求出符合条件的 。时间复杂度 (2) 对 105 的数据显然会超时。因为 ≤ 所以 一定是 1∼ 的后缀最小值。又因为 ∼ 中 最大即这段区间不能有任何一个数比 大。可以二分求出 的值。用单调栈 1 和 2 分别维护后缀最大值和最小值每次循环时在 2 上二分找出第一个大于 1.() 即栈顶的下标更新答案。时间复杂度 (log⁡) 。Code#includebits/stdc.h using namespace std; int main(){ int n; cinn; vectorint a(n1); for(int i1;in;i)cina[i]; vectorint s1,s2; int ans0; for(int r1;rn;r){ while(s1.size()a[s1.back()]a[r]) s1.pop_back(); while(s2.size()a[s2.back()]a[r]) s2.pop_back(); auto lupper_bound(s2.begin(),s2.end(),s1.back()); if(l!s2.end())ansmax(ans,r-*l1); s1.push_back(r); s2.push_back(r); } coutans; return 0; }P13889 子矩阵题意有一个 × 个整数组成的矩阵求所有大小为 × 的子矩阵中最大值与最小值的乘积的和。思路考虑暴力做法先找出每个子矩形再计算最小值和最大值统计答案时间复杂度 () 显然不能通过本题。我们可以使用单调队列进一步优化对于输入的 × 的矩阵我们可以把每一行看作一个单独的数列对其求出它的每个长度为 的子段的区间最大值易得出这样的最大值有 ×(−1) 个将每行的最大值构成新矩阵 1 的一行则 1 的大小是 ×(−1) 。对新矩阵再将它的每一列看作一个单独的数列求出这一列上每个长度为 的子段的区间最大值存到另一个矩阵 2 中 2 的大小就是 (−1)×(−1) 。最小值同理。经过这一步我们可以得出两个存储原矩阵的子矩阵最值的矩阵最后统计答案即可。Code#includebits/stdc.h using namespace std; int main(){ int n,m,a,b; cinnmab; vectorvectorint c(n1,vectorint(m1)); for(int i1;in;i){ for(int j1;jm;j){ cinc[i][j]; } } vectorvectorint mx1(n1,vectorint(m-b2)), mn1(n1,vectorint(m-b2)); vectorvectorint mx2(n-a2,vectorint(m-b2)), mn2(n-a2,vectorint(m-b2)); for(int i1;in;i){ dequeint q; for(int j1;jm;j){ while(q.size()q.front()j-b1)q.pop_front(); while(q.size()c[i][q.back()]c[i][j])q.pop_back(); q.push_back(j); if(jb)mx1[i][j-b1]c[i][q.front()]; } } for(int j1;jm-b1;j){ dequeint q; for(int i1;in;i){ while(q.size()q.front()i-a1)q.pop_front(); while(q.size()mx1[q.back()][j]mx1[i][j])q.pop_back(); q.push_back(i); if(ia)mx2[i-a1][j]mx1[q.front()][j]; } } for(int i1;in;i){ dequeint q; for(int j1;jm;j){ while(q.size()q.front()j-b1)q.pop_front(); while(q.size()c[i][q.back()]c[i][j])q.pop_back(); q.push_back(j); if(jb)mn1[i][j-b1]c[i][q.front()]; } } for(int j1;jm-b1;j){ dequeint q; for(int i1;in;i){ while(q.size()q.front()i-a1)q.pop_front(); while(q.size()mn1[q.back()][j]mn1[i][j])q.pop_back(); q.push_back(i); if(ia)mn2[i-a1][j]mn1[q.front()][j]; } } long long ans0; long long mod998244353; for(int i1;in-a1;i){ for(int j1;jm-b1;j){ ans(ans(mx2[i][j]*1LL*mn2[i][j]%mod))%mod; } } coutans; return 0; }