Codeforces 756C Nikita and stack

题目大意:

给定一个对栈进行操作的操作序列，初始时序列上没有任何操作，每一次将一个本来没有操作的位置变为某一操作(push(x),pop())。在每一次变化后输出按照顺序执行操作序列最后得到的栈顶元素。对空栈pop()没有任何作用。

题解:

容易发现我们只用关心栈顶元素，而不用管其他的元素
而一个被push的元素成为栈顶的条件是操作序列中在它后面的元素全部都被pop了
所以问题转化成了求最大的一个push的操作，满足在它后面的push和pop全部都互相抵消掉，不对栈造成影响。
我们可以使用线段树来维护这个东西:
- 把push操作当作1,pop操作当做-1
- 记录一下每段区间的sum
- 并且记录一下从右端开始的最大和连续子序列
查找嘛。。。自己YY去吧

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

inline int cat_max(const int &a,const int &b){return a>b ? a:b;}

inline int cat_min(const int &a,const int &b){return a<b ? a:b;}

const int maxn = 100010;

struct Node{

	int sum,rmx;

}T[maxn<<2];

inline void update(int rt){

	T[rt].sum = T[rt<<1].sum + T[rt<<1|1].sum;

	T[rt].rmx = cat_max(T[rt<<1|1].rmx,T[rt<<1].rmx + T[rt<<1|1].sum);

}

int pos,val;

void modify(int rt,int l,int r){

	if(l == r){

		T[rt].sum = T[rt].rmx = val;

		return;

	}

	int mid = l+r >> 1;

	if(pos <= mid) modify(rt<<1,l,mid);

	else modify(rt<<1|1,mid+1,r);

	update(rt);return;

}

int n;

int query(){

	int nw = 1,l = 1,r = n,sum = 0;

	if(T[nw].rmx <= 0) return -1;

	while(l != r){

		int mid = l+r >> 1;

		if(sum + T[nw<<1|1].rmx > 0){

			nw = nw<<1|1;

			l = mid+1;

		}else{

			sum += T[nw<<1|1].sum;

			nw = nw<<1;

			r = mid;

		}

	}return l;

}

int a[maxn];

int main(){

	read(n);

	int opt;

	for(int i=1;i<=n;++i){

		read(pos);read(opt);

		if(opt == 0){

			val = -1;

			modify(1,1,n);

		}else{

			val = 1;

			read(a[pos]);

			modify(1,1,n);

		}

		int ans = query();

		if(ans == -1) puts("-1");

		else printf("%d\n",a[ans]);

	}

	getchar();getchar();

	return 0;

}

巴特西

Codeforces 756C Nikita and stack

题目大意:

题解:

最新文章

热门文章