codeforces-760e-Nikita and stack-线段树

题目链接

日常抄题解系列……

题意：这个题目的题意有点难懂，他的样例给的太特殊了……一个健忘症儿童有一个栈并进行了m次操作，操作有两种，一是pop,一是push(x)。因为他有健忘症，所以他不能按顺序记出操作的顺序。他每次能回忆出一个操作的操作种类，是第几步的操作，如果是push还能回忆出x。没当他回忆出一个操作后，请你根据他已经回忆出的所有操作给出到最后一步的栈顶元素，如果栈为空那么输出-1。

思路：最最暴力的想法是每次输入一个操作之后，插入操作序列，然后暴力模拟一遍。但明显这个会超时，而且复杂度巨大。可以考虑，每当回忆出一个新的操作数时，前面计算过的信息是明显有用的，抛掉重复计算肯定是不合理的。所以我们可以考虑用前缀和来维护前面的进出栈信息，进栈+1,出栈-1。但是给出的步骤又不是连续的，也就是说每个+1、-1的管辖范围并不是从最后一步到第一步，而是有可能是中间某一步到第一步，所以可以考虑用线段树记录区间最大值来维护这个前缀和。进栈时将这个操作的步骤序列到第一步全部加一，出栈时减一。这样，如果线段树根的值大于0，说明栈里有元素，同时这个线段树的值又是单调减的，所以可以直接查处最后一个不是零的元素位置，这个位置的数就是最后的栈顶元素。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<iostream>
#define N 1000006 
#define lson (id<<1)
#define rson ((id<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
struct nod{
	int sum,lazy;
}tree[N*5];
int n,q;
int a[1000006];
void push_up(int id)
{
	tree[id].sum=max(tree[lson].sum,tree[rson].sum);
	return;
}
void build_tree(int id,int l,int r)
{
//	cout<<id<<' '<<l<<' '<<r<<' '<<mid<<endl;
	if (l==r)
	{
		tree[id].lazy=0;
		return;
	}
	build_tree(lson,l,mid);
	build_tree(rson,mid+1,r);
	push_up(id);
	tree[id].lazy=0;
	return;
}
void push_down(int id,int l,int r)
{
	tree[lson].sum+=tree[id].lazy;
	tree[lson].lazy+=tree[id].lazy;
	tree[rson].sum+=tree[id].lazy;
	tree[rson].lazy+=tree[id].lazy;
	tree[id].lazy=0;
	return;
}
void ins(int id,int l,int r,int ql,int qr,int tt)
{
	if (ql<=l && r<=qr)
	{
		tree[id].sum+=tt;
		tree[id].lazy+=tt;
		return;
	}
	if (tree[id].lazy) push_down(id,l,r);
	if (ql<=mid)
		ins(lson,l,mid,ql,qr,tt);
	if (mid+1<=qr)
		ins(rson,mid+1,r,ql,qr,tt);
	push_up(id);
	return;
}
int query(int id,int l,int r)
{
	if (l==r)
	{
		return l;
	}
	if (tree[id].lazy)
		push_down(id,l,r);
	int sum;	
    if(tree[rson].sum>0)
        sum=query(rson,mid+1,r);
      else sum=query(lson,l,mid);
	return sum;
}
int main()
{
	int m;
	scanf("%d",&m);
    build_tree(1,1,1000000);
    memset(a,0,sizeof(a));
    for(int i=1;i<=m;i++)
    {
    	int step,ch;
    	scanf("%d%d",&step,&ch);
    	if(ch==1)
    	{
    		int x;
    		scanf("%d",&x);
    		ins(1,1,1000000,1,step,1);
    		a[step]=x;
		}
		else
		ins(1,1,1000000,1,step,-1);
		if(tree[1].sum>0)
		 {
		  int pos=query(1,1,1000000);
	      printf("%d\n",a[pos]);
		 }
		else 
		 printf("-1\n"); 
	}
	return 0;
}