{"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 - the commander. So he tries to hire a commander, and he wants to choose the person who will be respected by warriors.\n\nEach 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_).\n\nInitially Vova's army is empty. There are three different types of events that can happen with the army:\n\n*   1 _p__i_ — one warrior with personality _p__i_ joins Vova's army;\n*   2 _p__i_ — one warrior with personality _p__i_ leaves Vova's army;\n*   3 _p__i_ _l__i_ — Vova tries to hire a commander with personality _p__i_ and leadership _l__i_.\n\nFor 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.\n\n## Input\n\nThe first line contains one integer _q_ (1 ≤ _q_ ≤ 100000) — the number of events.\n\nThen _q_ lines follow. Each line describes the event:\n\n*   1 _p__i_ (1 ≤ _p__i_ ≤ 108) — one warrior with personality _p__i_ joins Vova's army;\n*   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);\n*   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.\n\n## Output\n\nFor each event of the third type print one integer — the number of warriors who _respect_ the commander Vova tries to hire in the event.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"正如你从上一轮比赛中所记得的，Vova 正在玩一款名为《帝国怒火》的战略游戏。\n\nVova 成功组建了一支庞大的军队，但他忘记了军队中的核心人物——指挥官。因此，他试图雇佣一位指挥官，并希望选择一位能被战士们尊敬的人。\n\n每位战士由其个性表示——一个整数 #cf_span[pi]。每位指挥官有两个特征——他的个性 #cf_span[pj] 和领导力 #cf_span[lj]（均为整数）。战士 #cf_span[i] _尊重_ 指挥官 #cf_span[j] 当且仅当  （其中  是 #cf_span[x] 和 #cf_span[y] 的按位异或）。\n\n最初，Vova 的军队为空。有三种不同类型的事件可能发生：\n\n对于每个第三类事件，Vova 想知道有多少战士（仅统计已加入军队且尚未离开的）_尊重_ 他试图雇佣的指挥官。\n\n第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100000]) —— 事件的数量。\n\n接下来 #cf_span[q] 行，每行描述一个事件：\n\n对于每个第三类事件，请输出一个整数——在该事件中，尊重 Vova 试图雇佣的指挥官的战士数量。\n\n在示例中，前两个事件后，军队包含两个个性分别为 #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 再次尝试雇佣该指挥官时，没有战士尊重他。\n\n## Input\n\n第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100000]) —— 事件的数量。接下来 #cf_span[q] 行，每行描述一个事件：\n\n#cf_span[1 pi] (#cf_span[1 ≤ pi ≤ 10^8]) —— 一个个性为 #cf_span[pi] 的战士加入 Vova 的军队；\n#cf_span[2 pi] (#cf_span[1 ≤ pi ≤ 10^8]) —— 一个个性为 #cf_span[pi] 的战士离开 Vova 的军队（保证此时军队中至少存在一个这样的战士）；\n#cf_span[3 pi li] (#cf_span[1 ≤ pi, li ≤ 10^8]) —— Vova 尝试雇佣一个个性为 #cf_span[pi]、领导力为 #cf_span[li] 的指挥官。至少存在一个此类事件。\n\n## Output\n\n对于每个第三类事件，输出一个整数——尊重 Vova 在该事件中试图雇佣的指挥官的战士数量。\n\n[samples]\n\n## Note\n\n在示例中，前两个事件后，军队包含两个个性分别为 #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 再次尝试雇佣该指挥官时，没有战士尊重他。","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{Z} \\times \\mathbb{Z} $, where $ p $ is personality and $ l $ is leadership.  \n\n**Constraints**  \n1. $ 1 \\le q \\le 100000 $  \n2. For each event:  \n   - Type 1: Add warrior with personality $ p \\in \\mathbb{Z} $, $ 1 \\le p \\le 10^6 $  \n   - Type 2: Remove one occurrence of warrior with personality $ p \\in \\mathbb{Z} $, guaranteed to exist  \n   - Type 3: Query with commander $ (p, l) $, $ 1 \\le p, l \\le 10^6 $  \n\n**Objective**  \nFor each type-3 event with commander $ (p, l) $, compute:  \n$$\n\\left| \\left\\{ w \\in W \\mid (w \\oplus p) < l \\right\\} \\right|\n$$  \nwhere $ \\oplus $ denotes bitwise XOR.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF817E","tags":["bitmasks","data structures","trees"],"sample_group":[["5\n1 3\n1 4\n3 6 3\n2 4\n3 6 3","1\n0"]],"created_at":"2026-03-03 11:00:39"}}