社区 › 业界 › 学习笔记——单调数据结构

茅断卉 发表于 2026-2-15 17:00:27

学习笔记——单调数据结构

单调栈

题目

定义：一个下标 $i$ 是序列 $a$ 的后缀最大值下标当且仅当对于所有的 $i < j \le |a| $ ，都有 $a_i>a_j$。其中 $|a|$ 表示序列 $a$ 的长度。给出整数 $n$ 和一个长为 $n$ 的序列 $a$，对于每个 $1 \le i \le n$ ，输出 $a_1 \sim a_i$ 所有后缀最大值下标的异或和。
思路

考虑用一个栈来维护当前 $a_1 \sim a_i$ 所有的后缀最大值下标，容易发现栈中的数单调递增（指栈顶到栈底的下标对应的值单调递增）。当遍历到 $i$ 时，如果栈顶存放的下标 $j$ 满足 $a_j>a_i$，则因为栈是单调递增的，栈中的其他下标对应的值均大于 $a_i$，可以正确维护。如果不满足条件则需要不断弹出栈顶直到满足条件。并将 $i$ 入栈，栈中的下标即为后缀最大值下标
Code:

vector stk; int ans=0; for(int i=1;i>a>>b;   vector c(n+1,vector(m+1));   for(int i=1;ic;         }   }       vector mx1(n+1,vector(m-b+2)),   mn1(n+1,vector(m-b+2));   vector mx2(n-a+2,vector(m-b+2)),   mn2(n-a+2,vector(m-b+2));       for(int i=1;i

赵淳美 发表于 2026-2-18 13:20:07

鼓励转贴优秀软件安全工具和文档！

谧怏弦 发表于 2026-2-25 14:20:13

懂技术并乐意极积无私分享的人越来越少。珍惜

厂潺 发表于 2026-2-26 11:26:01

这个好，看起来很实用

连热 发表于 2026-2-28 11:32:53

谢谢分享，辛苦了

泠邸 发表于 2026-3-11 09:35:54

感谢分享，下载保存了，貌似很强大

鸠站 发表于 4 天前

yyds。多谢分享

时思美 发表于 3 天前

分享、互助 让互联网精神温暖你我

郦珠雨 发表于 昨天 20:28

鼓励转贴优秀软件安全工具和文档！

后仲舒 发表于 3 小时前

喜欢鼓捣这些软件，现在用得少，谢谢分享！

查看完整版本: 学习笔记——单调数据结构