T1 追忆
显然当 n≤mn\le mn≤m 时,需要 kkk 分钟才能将每一面都煎一遍;否则答案总是 ⌈nkm⌉\left\lceil\dfrac{nk}{m}\right\rceil⌈mnk ⌉。由于所有饼一共有 nknknk 面,至少需要这么长时间才可能能煎完所有饼;又因为 n>mn>mn>m,按照 1,2,3,…,n,1,2,3,…,n,…1,2,3,\dots,n,1,2,3,\dots,n,\dots1,2,3,…,n,1,2,3,…,n,… 的顺序每次取 mmm 个饼煎一次不可能取到重复的饼,且恰好能在这么长时间内煎完所有饼,我们证明了这个结论。
T2 无限水
可以发现新的格子变成水源后水域的周长不会变大,因此需要放置的冰块数下界为 ⌈n+m2⌉\left\lceil\dfrac{n+m}{2}\right\rceil⌈2n+m ⌉。下面给出一种能取到下界的构造:
* 若 n,mn,mn,m 不都是偶数,放第一行的 1,3,5,7,…1,3,5,7,\dots1,3,5,7,… 列和第一列的 3,5,7,…3,5,7,\dots3,5,7,… 行,若 nnn 是偶数,额外放 (n,1)(n,1)(n,1);若 mmm 是偶数,额外放 (1,m)(1,m)(1,m)。
* 若 n,mn,mn,m 都是偶数,放第一行的 1,3,5,…,m−11,3,5,\dots,m-11,3,5,…,m−1 列和最后一列的 2,4,6,⋯ ,n−22,4,6,\cdots,n-22,4,6,⋯,n−2 行,以及左下角 (n,1)(n,1)(n,1)。
容易证明这样的构造符合条件并且放置了恰好 ⌈n+m2⌉\lceil\frac{n+m}{2}\rceil⌈2n+m ⌉ 个冰块。
T3 无处存储
在输入时求出所有数的异或和 SSS,以及所有二进制下第 iii 位为 111 的数的异或和 SiS_iSi 。aaa 中出现两次的数在 SSS 中会被抵消,所以 S=x⊕yS=x\oplus yS=x⊕y。
又因为 x≠yx\not=yx=y,所以 S≠0S\not=0S=0。设 SSS 在二进制下的第 kkk 位为 111,则 x,yx,yx,y 在第 kkk 位分别为 0,10,10,1,只有一个数被计入 SkS_kSk ,所以两个数分别为 SkS_kSk 和 S⊕SkS\oplus S_kS⊕Sk ,按照大小顺序输出即可,空间复杂度 O(logai)O(\log a_i)O(logai )。
T4 攀登
使用并查集维护每个数所在的可重集,并对每个可重集维护包含可重集内所有大于 111 的数组成的链表 CCC、值为 000 的数的个数 AAA、值为 111 的数的个数 BBB 和可重集内所有数的和 SSS。
合并两个可重集 x,yx,yx,y 时,将两个链表 Cx,CyC_x,C_yCx ,Cy 合并得到新的 CCC,同时 A←Ax+AyA\leftarrow A_x+A_yA←Ax +Ay ,B←Bx+ByB\leftarrow B_x+B_yB←Bx +By ,S←Sx+SyS\leftarrow S_x+S_yS←Sx +Sy 。
对一个可重集 xxx 进行操作时,很容易计算不在链表中的数的贡献,若 v=0v=0v=0 则 A←AxA\leftarrow A_xA←Ax ,B←BxB\leftarrow B_xB←Bx ;若 v=1v=1v=1 则 A←BxA\leftarrow B_xA←Bx ,B←AxB\leftarrow A_xB←Ax 。对于链表中的数,我们直接暴力枚举每个数进行修改,若修改后小于等于 111 则从链表中删除并计入对 B,CB,CB,C 的贡献。
不难发现一个数 xxx 在进行 O(loglogx)O(\log\log x)O(loglogx) 次操作后就会变成 000 或 111,因此每个数只会被链表暴力枚举到 O(loglogai)O(\log\log a_i)O(loglogai ) 次,总时间复杂度 O(nloglogai+q)O(n\log\log a_i+q)O(nloglogai +q)。