【CodeForces】704A - Thor（队列，详解）

点击打开题目

A. Thor

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Thor is getting used to the Earth. As a gift Loki gave him a smartphone. There are n applications on this phone. Thor is fascinated by this phone. He has only one minor issue: he can't count the number of unread notifications generated by those applications (maybe Loki put a curse on it so he can't).

q events are about to happen (in chronological order). They are of three types:

1. Application x generates a notification (this new notification is unread).
2. Thor reads all notifications generated so far by application x (he may re-read some notifications).
3. Thor reads the first t notifications generated by phone applications (notifications generated in first t events of the first type). It's guaranteed that there were at least t events of the first type before this event. Please note that he doesn't read first t unread notifications, he just reads the very first t notifications generated on his phone and he may re-read some of them in this operation.

Please help Thor and tell him the number of unread notifications after each event. You may assume that initially there are no notifications in the phone.

Input

The first line of input contains two integers n and q (1 ≤ n, q ≤ 300 000) — the number of applications and the number of events to happen.

The next q lines contain the events. The i-th of these lines starts with an integer typei — type of the i-th event. If typei = 1 or typei = 2then it is followed by an integer xi. Otherwise it is followed by an integer ti (1 ≤ typei ≤ 3, 1 ≤ xi ≤ n, 1 ≤ ti ≤ q).

Output

Print the number of unread notifications after each event.

Examples

input

3 4
1 3
1 1
1 2
2 3

output

1
2
3
2

input

4 6
1 2
1 4
1 2
3 3
1 3
1 3

output

1
2
3
0
1
2

Note

In the first sample:

1. Application 3 generates a notification (there is 1 unread notification).
2. Application 1 generates a notification (there are 2 unread notifications).
3. Application 2 generates a notification (there are 3 unread notifications).
4. Thor reads the notification generated by application 3, there are 2 unread notifications left.

In the second sample test:

1. Application 2 generates a notification (there is 1 unread notification).
2. Application 4 generates a notification (there are 2 unread notifications).
3. Application 2 generates a notification (there are 3 unread notifications).
4. Thor reads first three notifications and since there are only three of them so far, there will be no unread notification left.
5. Application 3 generates a notification (there is 1 unread notification).
6. Application 3 generates a notification (there are 2 unread notifications).

感觉这道题有必要翻译一下：这题是说手机的app会发通知消息（强迫症表示分分钟清除掉），然后给我们三种操作：①某个app发出一条消息②阅读某个app的所有消息③阅读前num条未读消息（注意是前num条，不是经历过第二种操作后留下的消息，是全部消息的前num条，这一点看错了，你会到48组wa的，妈妈呀，太可怕了，48组才wa）

然后说一下方法：我们一共用两个队列一个数组，分别叫Q、time、vis，下面说一下含义：

Q []：储存每个app产生消息的时间（说是顺序也行，这个时间由ant变量记录）

time<pair<t , app> >：这个队列存的是数对，第一个元素表示产生的时间，第二个元素表示产生消息的app。

vis[]：记录这个位置的app是否已经弹出，在操作2中记录，在操作3中调用（这个不懂继续看下面思路）

如果碰见1操作：我们就把app进入的时间放进Q[ app ] 队列中，把该时间和app的序号放入time中。

操作2：我们弹出Q[ app ] 的全部元素，并且记录着弹出元素的位置到vis数组中。

操作3：我们从time队列依次取数，如果该app在2中已经弹出（通过查看vis数组实现），那么就不管，如果没有，那么就弹出Q[ app ] 的队首元素。

代码如下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
#define MAX 300000
queue<int> Q[MAX+11];
queue<pair<int,int> > time;
bool vis[MAX+11] = {false};
int main()
{
	int n,q;
	int op,num;
	scanf ("%d %d",&n,&q);
	int ant = 1;
	int ans = 0;
	while (q--)
	{
		scanf ("%d %d",&op,&num);
		if (op == 1)
		{
			ans++;
			Q[num].push(ant);
			time.push(make_pair(ant,num));
			ant++;
		}
		else if (op == 2)
		{
			while (!Q[num].empty())
			{
				vis[Q[num].front()] = true;		//在数组中去掉该点
				Q[num].pop();
				ans--; 
			}
		}
		else
		{
			while (!time.empty() && time.front().first <= num)
			{
				if (!vis[time.front().first])		//如果该点没有被去掉 
				{
					Q[time.front().second].pop();
					ans--;
				}
				time.pop();
			}
		}
		printf ("%d\n",ans);
	}
	return 0;
}