{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e阅读题目陈述:\u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME54/mandarin/STRQUER.pdf\"\u003e简体中文\u003c/a\u003e,\u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME54/russian/STRQUER.pdf\"\u003e俄语\u003c/a\u003e和\u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME54/vietnamese/STRQUER.pdf\"\u003e越南语\u003c/a\u003e。\u003c/h3\u003e\n厨师有一组整数 \u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eA\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ..., \u003cb\u003eA\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e。定义该集合的厨师数为连接该集合中的数字的惩罚的最小总和(每个数字必须至少与另一个数字连接),如果集合的大小大于或等于 \u003cb\u003e2\u003c/b\u003e,否则为 \u003cb\u003e0\u003c/b\u003e。数字 \u003cb\u003ex\u003c/b\u003e 和 \u003cb\u003ey\u003c/b\u003e 之间的连接的惩罚等于绝对值 |\u003cb\u003ex\u003c/b\u003e-\u003cb\u003ey\u003c/b\u003e|。厨师可以向集合中添加元素并从中删除元素,在每次这样的操作之后,他想要知道他的集合的厨师数。请帮助他解决这个复杂的任务。\n\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cp\u003e输入的第一行包含一个整数 \u003cb\u003eT\u003c/b\u003e,表示测试用例的数量。接下来是 \u003cb\u003eT\u003c/b\u003e 个测试用例的描述。\n每个测试用例的第一行包含两个正整数 \u003cb\u003eN\u003c/b\u003e,表示集合中的元素数量,和 \u003cb\u003eQ\u003c/b\u003e,表示厨师执行的操作数量。第二行包含 \u003cb\u003eN\u003c/b\u003e 个以空格分隔的整数 \u003cb\u003eA\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eA\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ..., \u003cb\u003eA\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e,表示集合 \u003cb\u003eA\u003c/b\u003e,集合中的所有数字两两不同。接下来的 \u003cb\u003eQ\u003c/b\u003e 行包含两个整数 - \u003cb\u003etype\u003c/b\u003e 和 \u003cb\u003ex\u003c/b\u003e。 \u003cb\u003etype\u003c/b\u003e \u003d 1 \u003cb\u003ex\u003c/b\u003e 表示厨师向集合中添加数字 \u003cb\u003ex\u003c/b\u003e,保证 \u003cb\u003ex\u003c/b\u003e 不在集合中。 \u003cb\u003etype\u003c/b\u003e \u003d 2 \u003cb\u003ex\u003c/b\u003e 表示厨师从集合中删除元素 \u003cb\u003ex\u003c/b\u003e,保证 \u003cb\u003ex\u003c/b\u003e 存在于集合中。\n\u003c/ul\u003e\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003e输出\u003c/h3\u003e\n每次厨师进行添加/删除操作后,输出集合 \u003cb\u003eA\u003c/b\u003e 的厨师数。\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003e约束\u003c/h3\u003e\n\u003cp\u003e应包含可能存在的输入数据的所有约束条件。格式如下:\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e1000\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e, \u003cb\u003eQ\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eA\u003csub\u003ei\u003c/sub\u003e \u003c/b\u003e, \u003cb\u003ex\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003etype\u003c/b\u003e ≤ \u003cb\u003e2\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e 所有测试用例中 \u003cb\u003eN\u003c/b\u003e 的总和 ≤ \u003cb\u003e2*10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e 所有测试用例中 \u003cb\u003eQ\u003c/b\u003e 的总和 ≤ \u003cb\u003e2*10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003e子任务\u003c/h3\u003e\n\u003cul\u003e\n \u003cli\u003e\u003cb\u003e子任务 #1: (27 分) \u003c/b\u003e 所有测试用例中 \u003cb\u003eN\u003c/b\u003e 的总和 ≤ \u003cb\u003e5*10\u003csup\u003e3\u003c/sup\u003e\u003c/b\u003e,所有测试用例中 \u003cb\u003eQ\u003c/b\u003e 的总和 ≤ \u003cb\u003e5*10\u003csup\u003e3\u003c/sup\u003e\u003c/b\u003e \u003c/li\u003e\n \u003cli\u003e\u003cb\u003e子任务 #2: (24 分) \u003c/b\u003e 所有测试用例中 \u003cb\u003eN\u003c/b\u003e 的总和 ≤ \u003cb\u003e5*10\u003csup\u003e4\u003c/sup\u003e\u003c/b\u003e,所有测试用例中 \u003cb\u003eQ\u003c/b\u003e 的总和 ≤ \u003cb\u003e5*10\u003csup\u003e4\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\n \u003cli\u003e\u003cb\u003e子任务 #3: (49 分) \u003c/b\u003e 原始约束\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e \u003c/p\u003e\n\n\u003ch3\u003e示例\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n1\n4 4\n1 7 2 4\n1 3\n1 6\n2 1\n2 7\n\n\u003cb\u003eOutput:\u003c/b\u003e\n5\n3\n3\n3.\n\u003c/pre\u003e\n\u003cp\u003e \u003c/p\u003e\n\u003ch3\u003e解释\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003e示例 1.\u003c/b\u003e 第一次操作后,\u003cb\u003eA\u003c/b\u003e \u003d {1, 7, 2, 4, 3},集合 \u003cb\u003eA\u003c/b\u003e 的厨师数可以通过下列连接计算得到:\u003cb\u003e1\u003c/b\u003e 和 \u003cb\u003e2\u003c/b\u003e,\u003cb\u003e2\u003c/b\u003e 和 \u003cb\u003e3\u003c/b\u003e,\u003cb\u003e7\u003c/b\u003e 和 \u003cb\u003e4\u003c/b\u003e,这些值的总和 |\u003cb\u003e1\u003c/b\u003e-\u003cb\u003e2\u003c/b\u003e|+|\u003cb\u003e2\u003c/b\u003e-\u003cb\u003e3\u003c/b\u003e|+|\u003cb\u003e7\u003c/b\u003e-\u003cb\u003e4\u003c/b\u003e|\u003d\u003cb\u003e5\u003c/b\u003e。第二次操作后,\u003cb\u003eA\u003c/b\u003e \u003d {1, 7, 2, 4, 3, 6},厨师数 \u003d |\u003cb\u003e1\u003c/b\u003e-\u003cb\u003e2\u003c/b\u003e|+|\u003cb\u003e4\u003c/b\u003e-\u003cb\u003e3\u003c/b\u003e|+|\u003cb\u003e7\u003c/b\u003e-\u003cb\u003e6\u003c/b\u003e| \u003d 3。第三次操作后,\u003cb\u003eA\u003c/b\u003e \u003d {7, 2, 4, 3, 6},厨师数 \u003d |\u003cb\u003e4\u003c/b\u003e-\u003cb\u003e3\u003c/b\u003e|+|\u003cb\u003e2\u003c/b\u003e-\u003cb\u003e3\u003c/b\u003e|+|\u003cb\u003e7\u003c/b\u003e-\u003cb\u003e6\u003c/b\u003e| \u003d 3。\u003c/p\u003e最后 \u003cb\u003eA\u003c/b\u003e \u003d {2, 4, 3, 6},厨师数 \u003d |\u003cb\u003e3\u003c/b\u003e-\u003cb\u003e2\u003c/b\u003e|+|\u003cb\u003e6\u003c/b\u003e-\u003cb\u003e4\u003c/b\u003e|\u003d3。"}}]}