文化课补完了，所以来改题。
T1 涂色 paint
弱智签到题，维护时间戳。
T2 幂次 power
近似原题：CodeForces-955C Sad Powers *2100
一个数可能会被统计多次，例如 \(2^{12}=4^6=8^4=16^3=64^2\)，考虑只在 \(2^{12}\)，即指数最大的位置记录答案，由于 \(1\) 比较特殊先不考虑。
可以得到 \(cnt_i=\left\lfloor\sqrt[i]{n}\right\rfloor-1\)，表示可以表示为 \(x=a^i\) 的个数。
于是要在 \(i\) 处删去 \(i\times j\) 次的贡献，也就是减去所有倍数的并，容斥：
\[\left|\bigcup_{i\in S} P_i\right|=\sum_{T\subseteq S,T\neq \varnothing} (-1)^{|T|} \left|\bigcap_{j\in T} P_j\right| \]显然多重集没有贡献，容斥系数是 \(\mu\)，集合交的大小也就是对应的 \(cnt\)。
这个复杂度在 CodeForces 里过不去，原因是单次 \(O(\log^2 n)\) 不够快。
容易发现 \(k\ge 3\) 时数据规模较小，可以暴力枚举底数和指数，并且这个支持预处理。
\(k=2\) 的部分可以用 \(\left\lfloor\sqrt{n}\right\rfloor\) 求出，但有重复部分，重复部分可以在暴力枚举 \(k\ge 3\) 时不统计指数为偶数的情况。
T3 圣诞树 tree
任意选四个点构成一个四边形，走对角线一定不是最优策略，同样路径也不能出现交叉。
这说明对于已经走到的区间 \([L,R]\) 下一个要去到的位置一定是 \(L-1\) 或 \(R+1\)，区间 DP 一下。
T4 密码锁 lock
\(k=1\)
直接输出最大值减最小值。
\(k=2\)
容易发现把较大值放一行，较小值放一行是更优的，证明考虑交换可能会增大答案。