题解

思路

先确定 $n$ 位于三角形编号的第几行、该行的第几列。设它位于第 $r$ 行第 $c$ 列。向上走到第 $q$ 行时，所有可能到达的列恰好形成一个连续区间：左端为 $\max(1,c-(r-q))$，右端为 $\min(q,c)$。

第 $q$ 行第 $j$ 列对应的基数为 $q(q-1)/2+j$，罐子编号是这个基数的平方。因此只需对每一行求一个连续平方和。

做法

用三角形数定位 $r,c$。预处理平方前缀和 $S(x)=1^2+2^2+\cdots+x^2$，或直接使用平方和公式。对于 $q=1,2,\ldots,r$，计算该行祖先列区间对应的连续基数范围 $[L,R]$，把 $S(R)-S(L-1)$ 加入答案。

任意倒下的罐都对应从 $(r,c)$ 连续向上选择左上或右上父节点得到的位置；走 $r-q$ 步后列偏移可以取连续的全部整数，正好得到上述区间。反之，区间中的每一列都能通过适当安排两种向上移动到达，所以统计既不遗漏也不重复。

复杂度

第 $r$ 行满足 $r=O(\sqrt n)$。每个测试用例的时间复杂度为 $O(\sqrt n)$，空间复杂度为 $O(1)$。