Problem : 299 - 比特集合

Problem Statistics

Solved Member: 5　　Submission: 24　　User Tried: 7

Statement:

瀚瀚有一個箱子，剛開始箱子裡面是空的。接著瀚瀚要對箱子做一些怪怪的操作：

1.Insert a：箱子裡放入一隻 a 歲的小雞
2.Delete b：將箱子裡面所有 b 歲的小雞都拿出來
3.Add c：時間過了 c 年，箱子裡的小雞都長大了 c 歲(歲數+c)
4.Q-bit d：瀚瀚想知道目前箱子裡的小雞中有幾隻歲數的二進位第 d 位數是 1

你可以假設小雞都長生不死，只要瀚瀚不把他拿出來，他們就會永遠在箱子裡面

我們可以將一隻小雞的歲數，假如 10 歲寫成二進位變成： 1010

這時候從右邊(最低位)數過來就分別為第 0 位、第 1 位、第 2 位......

對於二進位數字 1010 來說，第 0 位為 0，第 1 位為 1，第 2 位為 0......

Input:Output:

第一行有一個數字 n，代表有幾組操作

接下來 n 行，代表瀚瀚依序做的操作。每行最前面有一個字串，有可能為「Insert」、「Delete」、「Add」、「Q-bit」之一，後面接著一個數字，意義如上面敘述。
請注意操作是有先後順序的

限制：
1 ≤ n ≤ 500000
對於 Insert、Delete 操作， 0 ≤ a,b ≤ 1000000000
對於 Add 操作， 0 ≤ c ≤ 1000
對於 Q-bit 操作， 0 ≤ d ≤ 15

其中 20% 的測試資料滿足： n ≤ 200
其中 30% 的測試資料滿足： n ≤ 2000
其中 60% 的測試資料滿足： n ≤ 10000

對於每一個 Q-bit 詢問，請輸出一行，包含一個數字，代表箱子裡面有幾隻小雞符合詢問。

Sample Input:Sample Output:

8
Insert 1
Q-bit 0
Add 1
Q-bit 0
Q-bit 1
Delete 2
Insert 1
Q-bit 1

1
0
1
0

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	2000ms	524288kb
1-1	2000ms	524288kb	10
1-2	2000ms	524288kb
1-3	2000ms	524288kb
2-1	2000ms	524288kb	10
2-2	2000ms	524288kb
2-3	2000ms	524288kb
3-1	2000ms	524288kb	10
3-2	2000ms	524288kb
3-3	2000ms	524288kb
4-1	2000ms	524288kb	10
4-2	2000ms	524288kb
4-3	2000ms	524288kb
5-1	2000ms	524288kb	10
5-2	2000ms	524288kb
5-3	2000ms	524288kb
6-1	2000ms	524288kb	10
6-2	2000ms	524288kb
6-3	2000ms	524288kb
7-1	3000ms	524288kb	10
7-2	3000ms	524288kb
7-3	3000ms	524288kb
8-1	3000ms	524288kb	10
8-2	3000ms	524288kb
8-3	3000ms	524288kb
9-1	3000ms	524288kb	10
9-2	3000ms	524288kb
9-3	3000ms	524288kb
10-1	3000ms	524288kb	10
10-2	3000ms	524288kb
10-3	3000ms	524288kb