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

【CF簡(jiǎn)介】

題目鏈接：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).

題意：

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

解題：

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

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

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

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

?? 總的復(fù)雜度是O（n），因?yàn)槊織l消息最多只會(huì)產(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;
}