牛客小白月赛F（根号trick）

今天写牛客小白月赛的时候，做完前三题看到第四题是一个模拟，就没有写了，直接去看做的人数较多的F，做法直接让我大开眼界...
题目链接：牛客小白月赛F-困难卷积

题意：

给出两个序列 $a_i,b_i$ ，求出：

$\sum_{i=1}^{n} \sum_{j=1}^{n}\left \lfloor \sqrt{\left|a_{i}-b_{j}\right|} \right \rfloor$

范围是：
$1\le n\le 10^6, 0\le a_i,b_i \le 3\times 10^6, \Sigma a_i,\ \Sigma b_i\le 10^7$

思路

这里一开始注意到特殊的地方，也就是为什么给出 $a,b$ 序列的总和小于等于 $10^7$ ，重点就是在这里：

根号trick：序列 $a_i$ 中不同数字的个数小于等于 $\sqrt{\Sigma a_i}$

其实这么一想，已知总和 $sum$ ，问最多有多少个不同的 $a_i$ 来构成。我们可以用贪心的方法，例如上面的总和是 $10^7$ ，所以我们从最小的开始选，选 $1,2,3,\cdots$ ，假如最大选到 $m$ ，那么可以得出目前的总和是

$sum^\prime = 1+2+3+\cdots +m-1+m=\frac{(1+m)\times m}{2}\le sum=10^7$

所以能够得出来 $m$ 最多是 $\sqrt{2\times 10^7}=4472$ ，姑且算它 $5000$ 吧，所以这样平方级别的复杂度完全可以通过。

那么这个 $m=5000$ 能够说明什么呢？之前的 $n=10^6$ ，这样差别很大，说明一定一定一定有很多重复的数字，所以我们完全不用重复枚举，一个数字重复出现我们只算一次，具体请看代码就懂啦～

代码

map<int,int> mpa, mpb;
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>x, mpa[x]++;
    for (int i=1;i<=n;i++) cin>>x, mpb[x]++;
    for (auto &[x, na]:mpa)
        for (auto &[y, nb]:mpb)
            ans += (int)sqrt(Abs(x-y))*na*nb;
    cout<<ans;
}