THU2017spring 1-2 Company
描述
公司有n个员工，编号1 ~ n。员工数量众多，需要你为他们编写一个管理系统。
员工上班时都要登录管理系统登记一个code，离开要从管理系统上注销，员工也可以随时更新自己的code。到了下班时间，所有员工都会自动注销。公司管理人员随时都可能想要知道有多少员工上班，以及任一员工登记的code。
输入
第一行两个整数n、m。接下来m行，每行都是以下内容之一：
I a c //Log In：员工a登录，code为c。若a已登录，则将code更新为c
O a //Log Out：编号为a的员工注销。若a未登录，则注销无效
C //Close：到下班时间，所有员工注销
N //Number：询问有多少员工正在上班
Q a //Query：询问员工a的code（若未登录或已注销，视为-1）
输出
一个整数，是所有询问（N、Q）的答案之和（int表示，自动溢出，不用管溢出部分）
输入样例
10 8
I 1 2
I 1 4
Q 1
C
I 2 4
O 2
Q 2
N
输出样例
3
//“Q 1”答案是4，“Q 2”答案是-1，“N”答案是0，所有答案之和为3
限制
n <= 10,000,000
m <= 1,000,000
1<=a<=n
code为[0, 2^31)的整数
空间限制：256 MB
时间限制：2 sec
提示
一级提示
测试数据中，每种操作都可能频繁出现，或很少出现。因此，你的算法需要应对所有可能的情况。
● Bitmap / 常数时间初始化的数组
● Bitmap: 习题解析[2-34]，实例参考[2-35]，[2-36]
二级提示
● 避免频繁初始化整个数组。
● 可以借助Bitmap记录数组的各元素是否已被初始化。将一个（或所有）元素置为未初始化状态，实质上只需要打破“校验环”两个验证条件中的任何一个，考虑如何打破校验条件的复杂度最低。
● 还可以使用“懒删除”策略。
● 参考习题[2-34]。
用scanf(“%c”, …)或getchar()读入一个字符时，可能会读到空格、制表符、回车符或换行符，尽量避免使用这个方法。使用scanf(“%s”, …)会自动过滤空白字符。