{"problem":{"name":"【MX-S1-T2】催化剂","description":{"content":"小朋友们很喜欢糖果。 现在，小 K 有一些糖果，每个糖果上有一个数字代表它的种类。 有 $q$ 次事件，每次事件会加入一个糖果、或删除一个糖果、或提出一次询问。 每次询问会给出一个 $k$，表示小 K 现在需要将所有糖果分给 $k$ 个小朋友，并且每个小朋友都需要得到至少一个糖果。同时，小朋友们不喜欢得到相同的糖果。具体的，在一个小朋友得到了糖果 $i$ 时，如果 Ta 在这个糖果之前就已经","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10673"},"statements":[{"statement_type":"Markdown","content":"小朋友们很喜欢糖果。\n\n现在，小 K 有一些糖果，每个糖果上有一个数字代表它的种类。\n\n有 $q$ 次事件，每次事件会加入一个糖果、或删除一个糖果、或提出一次询问。\n\n每次询问会给出一个 $k$，表示小 K 现在需要将所有糖果分给 $k$ 个小朋友，并且每个小朋友都需要得到至少一个糖果。同时，小朋友们不喜欢得到相同的糖果。具体的，在一个小朋友得到了糖果 $i$ 时，如果 Ta 在这个糖果之前就已经获得过糖果 $i$，那么 Ta 就会感到非常生气，Ta 的愤怒值就会增加 $1$。\n\n小 K 不喜欢看到小朋友们生气，但小 K 无法解决这么困难的问题，所以你需要帮小 K 求出一种分糖果的方式，最小化所有小朋友的愤怒值之和。\n\n保证存在一种分糖果的方案，使得每个小朋友都分到至少一个糖果。\n\n每次询问并没有真正的分糖果，即每次询问后小 K 拥有的糖果不会改变。\n\n注意，分糖果的过程可以理解为将小 K 拥有的所有糖果划分到 $k$ 个非空序列，可以重排。\n\n## Input\n\n第一行两个正整数 $n,q$。\n\n第二行 $n$ 个正整数 $a_1,a_2,\\dots,a_n$，描述初始时小 K 拥有的糖果。\n\n接下来 $q$ 行，每行两个正整数，描述一次操作，共有三种可能的输入：\n\n`1 x`：表示小 K 又拥有了一个种类为 $x$ 的糖果。\n\n`2 x`：表示小 K 丢失了一个种类为 $x$ 的糖果，保证此时小 K 拥有至少一个种类为 $x$ 的糖果。\n\n`3 k`：表示此时小 K 需要把糖果分给 $k$ 个小朋友，你需要求出最小的所有小朋友的愤怒值之和。令 $S$ 表示此时小 K 拥有的糖果数量，保证 $1\\le k\\le S$。\n\n## Output\n\n对于每次询问，输出一行一个整数，表示你求出的答案。\n\n[samples]\n\n## Background\n\n原题链接：<https://oier.team/problems/S1B>。\n\n## Note\n\n__【样例解释 1】__\n\n第一次询问时，小 K 手上的糖果为 $\\{3,5,2,5,5\\}$，分给 $2$ 个小朋友的糖果为 $\\{2,3,5\\},\\{5,5\\}$，小朋友的愤怒值为 $0,1$。可以证明没有愤怒值之和更小的方案。\n\n__【数据范围】__\n\n__本题使用子任务捆绑测试。__\n\n对于 $100\\%$ 的数据，$1\\le n,q\\le 10^6$，$1\\le a_i,x\\le n$。每次询问时，令 $S$ 表示此时小 K 拥有的糖果数量，保证 $1\\le k\\le S$。\n\n| 子任务编号 | $n\\le $ | $q\\le $ | 特殊性质      | 分值 |\n| ---------- | ------- | ------- | ------------- | ---- |\n| $1$        | $5$     | $15$    | 无            | $20$ |\n| $2$        | $2000$  | $2000$  | 无            | $20$ |\n| $3$        | $10^5$  | $10^5$  | 无            | $20$ |\n| $4$        | $10^6$  | $10^6$  | $a_i,x\\le 50$ | $10$ |\n| $5$        | $10^6$  | $10^6$  | $k\\le 50$     | $10$ |\n| $6$        | $10^6$  | $10^6$  | 无            | $20$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10673","tags":["数学","贪心","线段树","树状数组","O2优化","梦熊比赛"],"sample_group":[["5 4\n3 5 2 5 5\n3 2\n2 5\n1 5\n3 1","1\n2"],["5 15\n2 5 2 5 1\n2 1\n1 1\n1 2\n1 4\n1 1\n3 2\n1 1\n3 1\n1 5\n3 1\n1 2\n3 1\n2 1\n3 3\n2 2\n","1\n5\n6\n7\n1\n"]],"created_at":"2026-03-03 11:09:25"}}