E. Choosing The Commander

Codeforces

IDCF817E

Time2000ms

Memory256MB

Difficulty—

bitmasksdata structurestrees

English · Original

Chinese · Translation

Formal · Original

As you might remember from the previous round, Vova is currently playing a strategic game known as Rage of Empires. Vova managed to build a large army, but forgot about the main person in the army - the commander. So he tries to hire a commander, and he wants to choose the person who will be respected by warriors. Each warrior is represented by his personality — an integer number _p__i_. Each commander has two characteristics — his personality _p__j_ and leadership _l__j_ (both are integer numbers). Warrior _i_ _respects_ commander _j_ only if ( is the bitwise excluding OR of _x_ and _y_). Initially Vova's army is empty. There are three different types of events that can happen with the army: * 1 _p__i_ — one warrior with personality _p__i_ joins Vova's army; * 2 _p__i_ — one warrior with personality _p__i_ leaves Vova's army; * 3 _p__i_ _l__i_ — Vova tries to hire a commander with personality _p__i_ and leadership _l__i_. For each event of the third type Vova wants to know how many warriors (counting only those who joined the army and haven't left yet) _respect_ the commander he tries to hire. ## Input The first line contains one integer _q_ (1 ≤ _q_ ≤ 100000) — the number of events. Then _q_ lines follow. Each line describes the event: * 1 _p__i_ (1 ≤ _p__i_ ≤ 108) — one warrior with personality _p__i_ joins Vova's army; * 2 _p__i_ (1 ≤ _p__i_ ≤ 108) — one warrior with personality _p__i_ leaves Vova's army (it is guaranteed that there is at least one such warrior in Vova's army by this moment); * 3 _p__i_ _l__i_ (1 ≤ _p__i_, _l__i_ ≤ 108) — Vova tries to hire a commander with personality _p__i_ and leadership _l__i_. There is at least one event of this type. ## Output For each event of the third type print one integer — the number of warriors who _respect_ the commander Vova tries to hire in the event. [samples] ## Note In the example the army consists of two warriors with personalities 3 and 4 after first two events. Then Vova tries to hire a commander with personality 6 and leadership 3, and only one warrior respects him (, and 2 < 3, but , and 5 ≥ 3). Then warrior with personality 4 leaves, and when Vova tries to hire that commander again, there are no warriors who respect him.

正如你从上一轮比赛中所记得的，Vova 正在玩一款名为《帝国怒火》的战略游戏。 Vova 成功组建了一支庞大的军队，但他忘记了军队中的核心人物——指挥官。因此，他试图雇佣一位指挥官，并希望选择一位能被战士们尊敬的人。每位战士由其个性表示——一个整数 #cf_span[pi]。每位指挥官有两个特征——他的个性 #cf_span[pj] 和领导力 #cf_span[lj]（均为整数）。战士 #cf_span[i] _尊重_ 指挥官 #cf_span[j] 当且仅当（其中是 #cf_span[x] 和 #cf_span[y] 的按位异或）。最初，Vova 的军队为空。有三种不同类型的事件可能发生：对于每个第三类事件，Vova 想知道有多少战士（仅统计已加入军队且尚未离开的）_尊重_ 他试图雇佣的指挥官。第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100000]) —— 事件的数量。接下来 #cf_span[q] 行，每行描述一个事件：对于每个第三类事件，请输出一个整数——在该事件中，尊重 Vova 试图雇佣的指挥官的战士数量。在示例中，前两个事件后，军队包含两个个性分别为 #cf_span[3] 和 #cf_span[4] 的战士。然后 Vova 尝试雇佣一个个性为 #cf_span[6]、领导力为 #cf_span[3] 的指挥官，只有其中一个战士尊重他（，且 #cf_span[2 < 3]，但，且 #cf_span[5 ≥ 3]）。接着，个性为 #cf_span[4] 的战士离开，当 Vova 再次尝试雇佣该指挥官时，没有战士尊重他。 ## Input 第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100000]) —— 事件的数量。接下来 #cf_span[q] 行，每行描述一个事件： #cf_span[1 pi] (#cf_span[1 ≤ pi ≤ 10^8]) —— 一个个性为 #cf_span[pi] 的战士加入 Vova 的军队； #cf_span[2 pi] (#cf_span[1 ≤ pi ≤ 10^8]) —— 一个个性为 #cf_span[pi] 的战士离开 Vova 的军队（保证此时军队中至少存在一个这样的战士）； #cf_span[3 pi li] (#cf_span[1 ≤ pi, li ≤ 10^8]) —— Vova 尝试雇佣一个个性为 #cf_span[pi]、领导力为 #cf_span[li] 的指挥官。至少存在一个此类事件。 ## Output 对于每个第三类事件，输出一个整数——尊重 Vova 在该事件中试图雇佣的指挥官的战士数量。 [samples] ## Note 在示例中，前两个事件后，军队包含两个个性分别为 #cf_span[3] 和 #cf_span[4] 的战士。然后 Vova 尝试雇佣一个个性为 #cf_span[6]、领导力为 #cf_span[3] 的指挥官，只有其中一个战士尊重他（，且 #cf_span[2 < 3]，但，且 #cf_span[5 ≥ 3]）。接着，个性为 #cf_span[4] 的战士离开，当 Vova 再次尝试雇佣该指挥官时，没有战士尊重他。

**Definitions** Let $ q \in \mathbb{Z} $ be the number of events. Let $ W \subseteq \mathbb{Z} $ be the multiset of current warriors' personalities. Each commander is a pair $ (p, l) \in \mathbb{Z} \times \mathbb{Z} $, where $ p $ is personality and $ l $ is leadership. **Constraints** 1. $ 1 \le q \le 100000 $ 2. For each event: - Type 1: Add warrior with personality $ p \in \mathbb{Z} $, $ 1 \le p \le 10^6 $ - Type 2: Remove one occurrence of warrior with personality $ p \in \mathbb{Z} $, guaranteed to exist - Type 3: Query with commander $ (p, l) $, $ 1 \le p, l \le 10^6 $ **Objective** For each type-3 event with commander $ (p, l) $, compute: $$ \left| \left\{ w \in W \mid (w \oplus p) < l \right\} \right| $$ where $ \oplus $ denotes bitwise XOR.

Samples

Input #1

Output #1

1
0

API Response (JSON)

{
  "problem": {
    "name": "E. Choosing The Commander",
    "description": {
      "content": "As you might remember from the previous round, Vova is currently playing a strategic game known as Rage of Empires. Vova managed to build a large army, but forgot about the main person in the army - ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF817E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "As you might remember from the previous round, Vova is currently playing a strategic game known as Rage of Empires.\n\nVova managed to build a large army, but forgot about the main person in the army - ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "正如你从上一轮比赛中所记得的，Vova 正在玩一款名为《帝国怒火》的战略游戏。\n\nVova 成功组建了一支庞大的军队，但他忘记了军队中的核心人物——指挥官。因此，他试图雇佣一位指挥官，并希望选择一位能被战士们尊敬的人。\n\n每位战士由其个性表示——一个整数 #cf_span[pi]。每位指挥官有两个特征——他的个性 #cf_span[pj] 和领导力 #cf_span[lj]（均为整数）。战士 #c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ q \\in \\mathbb{Z} $ be the number of events.  \nLet $ W \\subseteq \\mathbb{Z} $ be the multiset of current warriors' personalities.  \nEach commander is a pair $ (p, l) \\in \\mathbb...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments