【打CF，學算法——三星級】Codeforces 704A Thor (模擬)

【CF簡介】

題目鏈接：CF 704A

題面：

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 aren 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:

Application x generates a notification (this new notification is unread). Thor reads all notifications generated so far by application x (he may re-read some notifications). Thor reads the first t notifications generated by phone applications (notifications generated in firstt events of the first type). It's guaranteed that there were at leastt events of the first type before this event. Please note that he doesn't read firstt unread notifications, he just reads the very firstt 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 andq (1?≤?n,?q?≤?300?000)?— the number of applications and the number of events to happen.

The next q lines contain the events. Thei-th of these lines starts with an integertype_i?— type of thei-th event. If type_i?=?1 ortype_i?=?2 then it is followed by an integerx_i. Otherwise it is followed by an integert_i (1?≤?type_i?≤?3,?1?≤?x_i?≤?n,?1?≤?t_i?≤?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:

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

In the second sample test:

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

題意：

??? 此題背景是手機app產(chǎn)生未讀消息，有n款app，對應三種事件，事件一，x號app產(chǎn)生一條新的未讀消息。事件二，雷神讀了x號app的所有未讀信息。事件三，雷神讀了最開始的t條消息，（這些就是按順序產(chǎn)生的app消息，不管讀沒讀）。每次事件后，都要輸出當前的未讀消息數(shù)。

解題：

?? 解法中，數(shù)據(jù)結(jié)構(gòu)采用一個消息列表，記錄消息，一個數(shù)量數(shù)組，對應每個app未讀消息數(shù)，一個消息向量數(shù)組，對應每個app產(chǎn)生的消息記錄的下標，一個pos數(shù)組，記錄每個app當前已經(jīng)處理過最后一條信息的后一個位置，一個sum值記錄總未讀消息數(shù)，一個p值記錄時間順序上通過操作三當前處理過的最后一條消息位置。

??? 對應操作一，可以設計一個消息列表，每產(chǎn)生一條新的消息，記錄該消息的產(chǎn)生app編號，以及一個標志代表該條消息是否已讀，同時給該app對應的數(shù)量數(shù)組數(shù)量加一，該款app的向量數(shù)組記錄該條消息下標，未讀消息總數(shù)加一。

??? 對應操作二，可以從該款app的pos數(shù)組中獲取到該款app最后處理的一條未讀信息的后一個位置，并開始往后掃描讀，標記該條消息為已讀。同時，總未讀消息數(shù)減去該app對應未讀消息數(shù)，并將該app未讀消息數(shù)清零，更新最后處理未讀消息的后一個位置信息。

??? 對應操作三，只要從p（當前處理過最后一個位置開始處理即可），這個過程中會遇到未讀和已讀消息，已讀的直接跳過，未讀的需要標記已讀，同時總sum值（未讀消息數(shù)）減一，對應的該消息產(chǎn)生app的未讀數(shù)量數(shù)組的值也要減一。

?? 總的復雜度是O（n），因為每條消息最多只會產(chǎn)生一遍，讀一遍。

代碼：

#include#include#include#include#define?LL?long?long
#define?sz?300010
using?namespace?std;
struct?info
{
	int?id;
	bool?vis;
}store[sz];
int?amount[sz];
int?pos[sz];
vectorv[sz];
int?main()
{
????int?sum=0,n,q,a,b,p=0,cnt=0;
????scanf("%d%d",&n,&q);
????for(int?i=0;i<q;i++)
????{
????	scanf("%d%d",&a,&b);
????	if(a==1)
????	{
	????	v[b].push_back(cnt);
	????	amount[b]++;
	????	sum++;
	????	store[cnt].vis=0;
	????	store[cnt].id=b;
	????	cnt++;
	????}
	????if(a==2)
	????{
????		sum-=amount[b];
????		amount[b]=0;
????		for(int?j=pos[b];j<v[b].size();j++)
????		{
		????	store[v[b][j]].vis=1;
		????}
		????pos[b]=v[b].size();
????	}
????	if(a==3)
????	{
	????	for(int?j=p;j<b;j++)
	????	{
	????		if(!store[j].vis)
	????		{
		????		store[j].vis=1;
		????		sum--;
		????		amount[store[j].id]--;
		????	}
	????	}
	????	p=max(p,b);
	????}
	????printf("%dn",sum);
????}
	return?0;
}