模板 - 数据结构 - 栈/Stack
2024-08-24 01:18:07
普通的栈大家都会写，STL的栈据说默认实现方式是deque，没关系反正deque跑得飞快。
这里收录的是一些奇怪的栈，当然双栈实现的队列收录在队列里面。
对顶栈
众所周知，栈可以维护一系列前缀和，包括前缀最值。但是怎么维护全局的呢？当每次都只会修改栈顶（换句话说是顺序移动，而不是随机移动），那么可以用两个反方向的栈来维护这一段序列。
题意：要求实现一种数据结构，可以查询全局的前缀最大值，全局的前缀最小值，可在任意位置修改，不过修改光标是顺序而不是随机移动的。
这道题原本我是使用线段树来实现的，线段树支持维护随机移动的版本，事实上加入优化之后没有被卡的话真的飞快。但是最好的解法是使用栈来实现的。
把括号序列看作折线，合法的括号序列比如左右括号平衡，这个可以记录一个全局sum直接O(1)维护。栈可以维护前缀和以及前缀和的最大最小值，但是怎么实现全局的呢？非常简单：把光标右侧的压入反方向的栈里面，这样每次修改的只有两边栈的栈顶元素。
把折线从右往左看，全局的前缀最大值当然就是全局的最大值，所以就是两边栈的前缀最大值里面比较大的那个。最小值也是同理。(注意左右移动栈顶的时候符号会反向）
struct Stack {
static const int MAXN = 1000000;
static const int INF = 1061109567;
int s[MAXN + 5];
int mi[MAXN + 5];
int ma[MAXN + 5];
int top, sum;
void Clear() {
top = 0;
s[top] = 0;
mi[top] = INF;
ma[top] = -INF;
}
void Push(int v) {
++top;
s[top] = v;
sum += s[top];
mi[top] = min(mi[top - 1], sum);
ma[top] = max(ma[top - 1], sum);
}
void Pop() {
if(top) {
sum -= s[top];
--top;
}
}
int Top() {
return s[top];
}
int Min() {
return mi[top];
}
int Max() {
return ma[top];
}
} ;
struct Editor {
Stack LStack, RStack;
int cur, sum;
void LeftShift() {
if(cur == 1)
return;
RStack.Push(-LStack.Top());
LStack.Pop();
--cur;
}
void RightShift() {
LStack.Push(-RStack.Top());
RStack.Pop();
++cur;
}
void Clear() {
LStack.Clear();
RStack.Clear();
sum = 0;
RightShift();
}
void Update(int v) {
int pv = LStack.Top();
if(pv == v)
return;
LStack.Pop();
sum -= pv;
LStack.Push(v);
sum += v;
}
int Min() {
return min(LStack.Min(), RStack.Min());
}
int Max() {
return max(LStack.Max(), RStack.Max());
}
void Show() {
for(int i = 1; i <= LStack.top; ++i)
printf(" %d", LStack.s[i]);
printf(" |");
for(int i = RStack.top; i >= 1; --i)
printf(" %d", RStack.s[i]);
printf("\n");
}
} editor;
事实上前缀和不需要额外的空间去维护，保持一个当前前缀和，然后Push和Pop的时候顺便维护一个就可以了。
最新文章
- Photoshop 裁剪图片
- visual C++ 项目和解决方案的区别
- iOS学习13之OC NSString类
- discuz安装
- Iterator 迭代器（一）
- SVN技术交流提纲
- 【原创】Quartz代码详解
- 20 个用于处理页面滚动效果的 jQuery 插件
- DataSource , DataSink， DataSourceLoop
- Why Memory Barrier？
- html回车事件
- C#.Net操作XML方法二
- .NET编程规范
- 201521145048《java程序与设计》第9周学习总结
- 复习上学期的HTML+CSS（1）
- Geometric regularity criterion for NSE: the cross product of velocity and vorticity 4: $u\cdot \om$
- Mysql 锁和锁算法
- HTML学习感悟
- 9. 一个list拆分成多个list返回
- windows多线程（一） 创建线程 CreateThread