线段树教做人系列（1）HDU4967 Handling the Past

题意：给你n组操作，分别为压栈，出栈，询问栈顶元素。每一组操作有一个时间戳，每次询问栈顶的元素的操作询问的是在他之前出现的操作，而且时间戳小于它的情况。题目中不会出现栈为空而且出栈的情况。

例如：

push 100 1

peak 6

push 200 5

询问的结果是100。

思路：先把时间戳离散化，我们把压栈看成在这个操作所在的时间+1，出栈看成-1，那么询问操作可以看成从询问的时间开始，找一段最短的后缀，并且后缀和大于0。所以我们在线段树中维护区间和和后缀和，查询的时候先搜索右半区间，如果右半区间的后缀和小于0，那把右半区间的和加上，再去查询左半区间。

代码：

#include <bits/stdc++.h>

#define ls(x) (x << 1)

#define rs(x) ((x << 1) | 1)

using namespace std;

const int maxn = 50010;

int ans;

struct op {

	int id, time, val;

};

op a[maxn];

int mp1[maxn], mp2[maxn], b[maxn];

struct SegementTree {

	int psum, sum;

};

SegementTree tr[maxn * 4];

void maintain(int o) {

	tr[o].sum = tr[ls(o)].sum + tr[rs(o)].sum;

	tr[o].psum = max(tr[rs(o)].psum, tr[rs(o)].sum + tr[ls(o)].psum);

}

void init(int o, int l, int r) {

	if(l == r) {

		tr[o].sum = tr[o].psum = 0;

		return;

	}

	int mid = (l + r) >> 1;

	init(ls(o), l ,mid);

	init(rs(o), mid + 1, r);

	maintain(o);

}

void insert(int o, int l, int r, int pos, int val) {

	if(l == r) {

		tr[o].sum += val;

		tr[o].psum += val;

		return;

	}

	int mid = (l + r) >> 1;

	if(pos <= mid) insert(ls(o), l, mid, pos, val);

	else insert(rs(o), mid + 1, r, pos, val);

	maintain(o);

}

int query(int o, int l, int r, int ql, int qr, int now) {

	int tmp = 0;

	if(ql <= l && r <= qr) {

		if(tr[o].psum + now <= 0) return tr[o].sum;

		else {

			if(l == r) {

				ans = l;

				return tr[o].sum;

			}

		}

	}

	int mid = (l + r) >> 1;

	if(qr > mid) tmp = query(rs(o), mid + 1, r, ql, qr, now);

	if(ans != -1) return tmp;

	tmp += query(ls(o), l, mid, ql, qr, now + tmp);

	return tmp;

}

char s[10];

int main() {

	int n, x, y, kase = 0;

	while(~scanf("%d", &n) && n) {

		init(1, 1, n);

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

			scanf("%s", s + 1);

			if(s[2] == 'u') {

				scanf("%d%d", &x, &y);

				a[i] = (op){1, y, x};

				b[i] = y;

			} else if(s[2] == 'o') {

				scanf("%d", &x);

				a[i] = (op){2, x, 0};

				b[i] = x;

			} else {

				scanf("%d", &x);

				a[i] = (op){3, x, 0};

				b[i] = x;

			}

		}

		sort(b + 1, b + 1 + n);

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

			int pos = lower_bound(b + 1, b + 1 + n, a[i].time) - b;

			mp1[pos] = i;

			mp2[i] = pos;

		}

		printf("Case #%d:\n", ++kase);

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

			if(a[i].id == 1)

				insert(1, 1, n, mp2[i], 1);

			else if(a[i].id == 2)

				insert(1, 1, n, mp2[i], -1);

			else {

				ans = -1;

				query(1, 1, n, 1, mp2[i], 0);

				if(ans == -1) printf("-1\n");

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

			}

		}

	}

}

巴特西

线段树教做人系列（1）HDU4967 Handling the Past

最新文章

热门文章