树状数组+STL FZU 2029 买票问题

 

题目传送门

题意:中文题面

分析:隔了一个考试周再做,开始没有什么思路,感觉能用线段树/树状数组维护,树状数组维护最小值不会去写线段树,结果超时.后来发现只要维护前缀几个人以及用优先队列/set维护最小忍受值,加上队列编号pop就能实现全部功能了.

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct BIT	{
	int sum[N], sz;
	void init(int n)	{
		sz = n;
		memset (sum, 0, sizeof (sum));
	}
	void updata(int i, int x)	{
		while (i <= sz)	{
			sum[i] += x;
			i += i & (-i);
		}
	}
	int query(int i)	{
		int ret = 0;
		while (i > 0)	{
			ret += sum[i];	i -= i & (-i);
		}
		return ret;
	}
}bit;
bool vis[N];

int main(void)	{
	int T;
	while (scanf ("%d", &T) == 1)	{
		priority_queue<P, vector<P>, greater<P> > que;	map<int, int> id;
		char str[10];	int left = 1, right = 0, n = 100000;
		bit.init (n);
		memset (vis, false, sizeof (vis));
		while (T--)	{
			scanf ("%s", &str);
			if (str[0] == 'a')	{
				int a, b;	scanf ("%d%d", &a, &b);
				id[a] = ++right;
				que.push (make_pair (b, id[a]));
				bit.updata (id[a], 1);		
			}
			else if (str[0] == 'c')	{
				int x, y;	scanf ("%d%d", &x, &y);
				if (id[x] < 1 || id[x] > right || vis[id[x]])	continue;
				int num = bit.query (id[x] - 1);
				printf ("%d\n", num);
				if (num > y)	{
					vis[id[x]] = true;
					bit.updata (id[x], -1);
				}
			}
			else if (str[0] == 'l')	{
				while (!que.empty ())	{
					P p = que.top ();	que.pop ();
					int aa = p.second, bb = p.first;
					if (vis[aa])	continue;
					vis[aa] = true;
					bit.updata (aa, -1);
					break;
				}
			}
			else if (str[0] == 'p')	{
				while (left <= right && vis[left])	left++;
				if (left > right)	continue;
				vis[left] = true;
				bit.updata (left, -1);
				left++;
			}
		}
	}

	return 0;
}