dTest21
contest20201101
B 第一题
题意
给定 $n,m$，问有多少正整数对 $(a,b)$ 满足 $a\le n, b\le m$ 且 $(\sqrt a + \sqrt b)^2\in Z$。
$n,m\le 2\times 10^6$。
题解
考场上解出来了。感觉比较简单。题意中的式子可以简化为 $ab$ 为完全平方数。
于是我们可以通过枚举 $a$，然后质因数分解每一个枚举的 $a$，计算有多少个符合的 $b$。复杂度 $O(n\sqrt n)$。
由于我们只需要知道 $a$ 除去自己的所有偶数因子是几，然后这个可以通过筛的方法去做。复杂度 $\sum \sqrt{\frac{n}{i}}=\sqrt n\sum i^{-\frac{1}{2}}=O(n)$。
C 消除贫困
题意
给定一个序列，支持两种操作。一，单点修改为 $x$。二，集体 $a_i=max(a_i,x)$。问最终的序列。
$n,q\le 2\times 10^5$。
题解
一道很智障的题目，但是考场上竟然没有想出来。
对于一个数，唯一对他有用的单点修改为他的最后一次单点修改，对他可能有用的集体扶贫为在他最后一次单点修改后的 $x$ 最大的集体扶贫。扫一遍统计后缀最大值即可。