[原创]codeforces 704A Thor [技巧吧.]

Tabris

CSDNSTLcodeforces思维

发布于：2016年8月10日

次浏览

[原创]codeforces 704A Thor [技巧吧。]

2016-08-10 15:19:05 Tabris_ 阅读数：556

博客爬取于 2020-06-14 22:43:56
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52171819

题目连接 : http://codeforces.com/problemset/problem/704/A

--------------------------------------.
A. Thor
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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:

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 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 = 2 then 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:

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).

----------------------------------.
题目大意 :
就是你有一个手机 有三种操作
1,x 软件收到一个信息
2，看了所有 x 软件的信息
3，看了第 1~第 x 次收到的信息 （被看过的也算）

每次都输出一下当前手机里的未读信息的个数

题解 ：
首先把信息编号
用一个 vector 和 set 维护下就好了
vector 有 n 个 代表 n 个软件 每次向 n[x]中加入新的信息编号
set 存储所有的信息

维护的时候
对于 1 操作 把信息编号加入 vector 和 set
对于 2 操作 对应 n[x]遍历一遍 从 set 中删除
对于 3 操作 遍历 1~x 从 set 中删除 （这里注意每次的 x 要记录一下 然后下一次遍历的时候只要遍历这个 x 到下一个 x 的区间就行了 之前被删除的不用再删除一遍 否则会 TLE）
每次输出 set 的大小就行了

这样总体复杂度是 O(2n)

/**************** 这些 shi 牢骚
这道题是赛后补得 并且看了网上的题解
当时 想到了思路 当时没有做主要是怕 TLE 在一个不太会用 set （我是小白） 当时想到的是对数组二分查找整个区间 然后删除 当对判断数据的统计这一块只想到了线段树（赛前几天才学习数据结构，做什么题都想用线段树） 然后旁边队友 风骚的 A 了这道题后 告诉用 STL 做 然而对于不会 STL 的我老说 根本没法搞。 So 我就不做了。。。
仔细想来 根本不用那么麻烦 多熟练下 vector map set 这东西其实是能秒的。。
****************/
附本题代码
-------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 300010;

vector<int> app[maxn];
set<int> cnt;

int main()
{
    int n,q,x,type,num;
    while(~scanf("%d%d",&n,&q))
    {
        num = 0;
        cnt.clear();
        int last = 0;
        for(int i=0;i<q;i++)
        {
            scanf("%d%d",&type,&x);
            if(type==1)
            {
                app[x].push_back(++num);
                cnt.insert(num);
            }
            else if(type==2)
            {
                for(int i=0;i<app[x].size();i++)
                    cnt.erase(app[x][i]);
                app[x].clear();
            }
            else
            {
                for(int i=last;i<=x;i++)
                {
                    cnt.erase(i);
                }
                last = max(x,last);
            }
            printf("%d\n",cnt.size());
        }
    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN

codeforces