题解 P1165 【日志分析】
t162
2020-01-19 11:28:27
[博客效果更佳](https://bambusoideae.cn/posts/Solutions/luogu-p1165.html)
这道题目很简单，只是一道栈的模拟题。至于最大值，我们可以用平衡树来维护。
操作：
- 操作0：把$X$压入栈，并插入到平衡树中；
- 操作1：从平衡树中删除栈顶元素，并从栈中弹出栈顶元素；
- 操作2：查找平衡树中最大元素（一直往右子树找，没有右子树了就返回）；
~~于是我们就愉快地解决了。~~
```cpp
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<stack>
using namespace std;
struct nodes{
int rd,x,lc,rc,cnt;
nodes(int X){
lc=rc=0;
x=X;
rd=rand();
cnt=1;
}
nodes(){
lc=rc=0;
x=0;
cnt=0;
}
};
nodes node[200001];
int root,cnt;
int newNode(int x){
node[cnt++]=nodes(x);
return cnt-1;
}
void zig(int x,int f){
int temp=node[node[x].lc].rc;
node[node[x].lc].rc=x;
if(x==root)root=node[x].lc;
else{
if(node[f].lc==x){
node[f].lc=node[x].lc;
}else node[f].rc=node[x].lc;
}
node[x].lc=temp;
}
void zag(int x,int f){
int temp=node[node[x].rc].lc;
node[node[x].rc].lc=x;
if(x==root)root=node[x].rc;
else{
if(node[f].lc==x){
node[f].lc=node[x].rc;
}else node[f].rc=node[x].rc;
}
node[x].rc=temp;
}
void insert(int &nd,int f,int x){ //插入
if(nd==0){
nd=newNode(x);
return;
}
if(x<node[nd].x){
insert(node[nd].lc,nd,x);
if(node[node[nd].lc].rd>node[nd].rd){
zig(nd,f);
}
}else if(x>node[nd].x){
insert(node[nd].rc,nd,x);
if(node[node[nd].rc].rd>node[nd].rd){
zag(nd,f);
}
}else{
node[nd].cnt++;
}
}
void del(int &nd,int f,int x){ //删除
if(node[nd].x==x){
if(node[nd].cnt>1){
node[nd].cnt--;
return;
}
if(node[nd].lc+node[nd].rc==0){
nd=0;
return;
}
if(node[nd].lc==0){
int t=node[nd].rc;
zag(nd,f);
del(nd,t,x);
return;
}
if(node[nd].rc==0){
int t=node[nd].lc;
zig(nd,f);
del(nd,t,x);
return;
}
if(node[node[nd].lc].rd>node[node[nd].rc].rd){
int t=node[nd].lc;
zag(nd,f);
del(nd,t,x);
}else{
int t=node[nd].rc;
zig(nd,f);
del(nd,t,x);
}
}else{
if(x<node[nd].x){
del(node[nd].lc,nd,x);
}else{
del(node[nd].rc,nd,x);
}
}
}
int query(int nd){ //查询
if(node[nd].rc==0){
return node[nd].x;
}else return query(node[nd].rc);
}
stack<int> sta;
int main(){
int n;
root=newNode(0);
scanf("%d",&n);
while(n--){
int x,y;
scanf("%d",&x);
if(x==0){
scanf("%d",&y);
insert(root,0,y);
sta.push(y);
}else if(x==1){
if(sta.empty())continue;
del(root,0,sta.top());
sta.pop();
}else{
if(sta.empty())puts("0");
else printf("%d\n",query(root));
}
}
}
```
---
如果你看懂了，恭喜你；如果没看懂，没关系，还有另一种做法。毕竟这是一道入门题。
思考：**难道栈中存的一定是输入的内容吗？**
**未必。**
我们发现，当压入的一个数$X$不比之前栈中所有数大的时候，它的压入与弹出对栈内数的最大值是没有任何影响的。
为什么呢？因为比$X$之前入栈的一些数中有比它大的数。要想让$X$成为栈中的最大数，就必须把比它之前入栈的所有比它大的数都弹出去。由于题目要求只能入栈一次，所以以上操作显然违背了栈的定义。
当$X$大于之前栈中所有的数的时候，它的压入与弹出对栈内数的最大值有影响，但对之前栈内的最大值无影响。
所以我们栈中存的数据是在入库之后仓库内所有集装箱的最大重量。
代码：
```cpp
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
stack<int> sta;
int main(){
int n;
scanf("%d",&n);
while(n--){
int x,y;
scanf("%d",&x);
if(x==0){
scanf("%d",&y);
if(sta.empty())sta.push(y);
else sta.push(max(sta.top(),y));
}else if(x==1){
if(sta.empty())continue;
sta.pop();
}else{
if(sta.empty())puts("0");
else printf("%d\n",sta.top());
}
}
}
```