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

单调栈

题目

定义：一个下标 $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:

[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[j];         }     }       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

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