[THUPC 2024 初赛] 分治乘法

小艾想要挑战分治乘法。TA 将策略抽象成了如下问题： 现在给定一个目标集合 $T$，该集合是 $\{1,\dots,n\}$ 的一个子集（$1\leq n\leq 5\times 10^5$）。你需要通过一系列操作构造一些集合最后得到 $T$，具体来说有以下三种操作： - 创造一个大小为一的集合 $|S|=1$。 - 将已经被构造出的两个不交集合 $A, B$ 并起来，得到 $A\cup B$。 - 将已经被构造出的一个集合 $A$ 进行平移，也即 $A+x = \{ a+x : a\in A \}$。 一个已经被构造出的集合可以在之后被使用多次。同时你需要保证操作过程中出现的所有集合都是 $\{1,\dots,n\}$ 的子集。 你的代价是构造出的所有集合的大小之和，你不需要最小化代价，只需要让代价控制不超过 $5\times 10^6$ 即可。你用的操作数量也不应超过 $10^6$。 ## Input 第一行输入一个正整数 $n$。 接下来一行输入一个 `01` 串，长度为 $n$，第 $x$ 位为 `1` 表示 $x\in T$，否则 $x\notin T$，保证 $T$ 非空。 ## Output 第一行输出一个正整数 $m$ 表示你使用的操作数量。 接下来 $m$ 行，每行描述一个操作，设第 $i$ 次操作得到的集合为 $T_i$： - `1 x` 表示创造一个大小为一的集合 $\{x\}$。 - `2 x y` 表示将不交集合 $T_x, T_y$ 并起来。 - `3 x y` 表示将已经被构造出的一个集合进行平移，也即 $T_x+y$。 你需要保证所有操作满足题目要求，并且最后一次操作产生的集合是 $T$。 [samples] ## Note ### 样例 \#1 解释 - 第一次操作：创造集合 $T_1=\{1\}$。 - 第二次操作：创造集合 $T_2=\{4\}$。 - 第三次操作：将 $T_1, T_2$ 并起来，得到 $T_3=\{1,4\}$。 - 第四次操作：将 $T_3$ 平移 $1$，得到 $T_4=\{2,5\}$。 - 第五次操作：将 $T_3, T_4$ 并起来，得到 $T_5=\{1,2,4,5\}$。这就得到了 $T$。 这个方案的总代价是 $1 + 1 + 2 + 2 + 4 = 10$。 ### 提示 如果你的复杂度是好的，请相信常数。 ### 题目使用协议 来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。 以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)） 1. 任何单位或个人都可以免费使用或转载本仓库的题目； 2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限； 3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。