tunnel warfare[pku2892].cpp

PKU 上的几个题目 Tunnel Warfare Unique Solution Washing Clothes Weather Forecast Who Gets the Most Ca

// PKU 2892
// HDOJ 1540
// segment tree with search
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;

const int LMAX = 50100;
const int EMAX = 17;
bool tree[1<<EMAX];
int n, m;

void update(int root, int vil, int l, int r, bool flag)
{
	if (l == r)
	{
		tree[root] = flag;
		return ;
	}
	int mid = (l+r) >> 1;
	if (vil <= mid)
		update(root<<1, vil, l, mid, flag);
	else
		update((root<<1)+1, vil, mid+1, r, flag);

	tree[root] = tree[root<<1] || tree[(root<<1)+1];
}

bool lflag, rflag;
int query(int root, int vil, int l, int r)
{
	if (! tree[root])
		return r - l +1;

	if (l == r)
	{
		if (vil < l)
			rflag = false;
		else if (l < vil)
			lflag = false;
		else
			lflag = rflag = false;
		return 0;
	}

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

	if (vil <= mid)
		ret = query(root<<1, vil, l, mid);
	else
		ret = query((root<<1)+1, vil, mid+1, r);

	if (lflag && vil > mid)
		ret += query(root<<1, vil, l, mid);
	if (rflag && vil <= mid)
		ret += query((root<<1)+1, vil, mid+1, r);

	return ret;
}

int main()
{
	int i, j, pre, pos;
	char cmd[3];
	stack <int> dvil;

	while ( scanf("%d %d", &n, &m) == 2 )
	{
		/*
		while (! dvil.empty())
			dvil.pop();
		memset(tree, 0, sizeof(tree));
		*/

		for (i=0; i<m; i++)
		{
			scanf("%s", cmd);
			if (cmd[0] == 'D')
			{
				scanf("%d", &pos);
				update(1, pos, 1, n, true);
				dvil.push(pos);
			}
			else if (cmd[0] == 'Q')
			{
				scanf("%d", &pos);
				lflag = rflag = true;
				printf("%d\n", query(1, pos, 1, n));
			}
			else
			{
				pre = dvil.top();
				dvil.pop();
				update(1, pre, 1, n, false);
			}
		}
	}
}