CF1600~1700

1731C

\(a\) 的质因子为奇数个，当且仅当 \(a\) 是平方数。

我们考虑如何处理出有多少段的异或和为平方数。

枚举平方数 \(p\)，枚举左端点 \(l\)，问题就变成了有多少 \(r\) 使得 \(\oplus_l^ra_i=p\)，处理出异或前缀和 \(s_i=\oplus_1^ia_i\)，查询有多少 \(r\) 使得 \(s_r\oplus s_{l-1}=p\) 即可。变形成 \(s_r=p\oplus s_{l-1}\)，这个东西可以递推处理出来。时间复杂度 \(O(n\sqrt{n})\)，注意数组开大一点，多处理一点平方数。

code

1730B

考虑二分代价 \(k\)，\(k\ge\max t_i\)。

显然每个点的代价不能超过 \(k\)。将绝对值拆开得到：

对于 \(n\) 组不等式求解集即可。二分过程中记录一下答案。

卡了一会，一开始没想到暴力求解集就行。

时间复杂度 \(O(n\log n)\)。

code