【打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 integertypei — type of thei-th event. If typei = 1 ortypei = 2 then it is followed by an integerxi. Otherwise it is followed by an integerti (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:
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产生未读消息，有n款app，对应三种事件，事件一，x号app产生一条新的未读消息。事件二，雷神读了x号app的所有未读信息。事件三，雷神读了最开始的t条消息，（这些就是按顺序产生的app消息，不管读没读）。每次事件后，都要输出当前的未读消息数。
解题：
解法中，数据结构采用一个消息列表，记录消息，一个数量数组，对应每个app未读消息数，一个消息向量数组，对应每个app产生的消息记录的下标，一个pos数组，记录每个app当前已经处理过最后一条信息的后一个位置，一个sum值记录总未读消息数，一个p值记录时间顺序上通过操作三当前处理过的最后一条消息位置。
对应操作一，可以设计一个消息列表，每产生一条新的消息，记录该消息的产生app编号，以及一个标志代表该条消息是否已读，同时给该app对应的数量数组数量加一，该款app的向量数组记录该条消息下标，未读消息总数加一。
对应操作二，可以从该款app的pos数组中获取到该款app最后处理的一条未读信息的后一个位置，并开始往后扫描读，标记该条消息为已读。同时，总未读消息数减去该app对应未读消息数，并将该app未读消息数清零，更新最后处理未读消息的后一个位置信息。
对应操作三，只要从p（当前处理过最后一个位置开始处理即可），这个过程中会遇到未读和已读消息，已读的直接跳过，未读的需要标记已读，同时总sum值（未读消息数）减一，对应的该消息产生app的未读数量数组的值也要减一。
总的复杂度是O（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;
}
下载文档
