最近完成的一些算法题

一个多月没写博客了，赶紧填个坑。

离上一篇博客居然已经过去一个多月啦，看来研究生还是要比本科忙多了，每天都有事情要做。最近呢，就是参加了昨天的Google Kickstart Round G 2018，本来顺利做完了2.5题，做完的时候有60名左右，结果有个大数据犯了一个低级错误，结果一个大数据挂了，最后只有100多名！啊！好气啊！看了一下题解，发现方法和我自己实现的方法差挺多的，所以想简单讲一下我的算法。

Problem A. Product Triplets

这道题，就是给你一个序列$A_n,n\leq7000$，让你计算满足$A_i,A_j,A_k$三个数中任意两个数乘积等于第三个数的这样的$(i,j,k) , i \lt j \lt k$三元组的个数。

题解中给出的方法是使用HashSet存入每个数，同样也可以使用二分。注意到序列的顺序无关，因此我们可以先将数列排序，然后枚举i和j，注意到在绝大多数情况下，$A_i*A_j \geq A_i,A_j$。因此我们要找的乘积一定在$A_i$和$A_j$的右边，而由于整个序列是有序的，因此我们可以通过二分来快速找到相应的值，伪代码如下所示。

for i = 1 to n
    for j = i + 1 to n
        binary_search A[i] * A[j] from A[j + 1] to A[n]
        answer ← answer + count(A[i] * A[j])

由于我们需要求出序列中$A_i * A_j$的个数，因此在C++中，可以分别调用lower_bound和upper_bound来求出上界和下界，然后相减即可求出个数。

前面提到在大多数情况下$A_i*A_j \geq A_i,A_j$是成立的，那么是否有不成立的情况呢？有的，在$A_i=0$或者$A_j=0$的时候等式就不成立了。这个时候三元组对应的序列就变成了$(0, 0, A_k)$。因此在排好序的序列中，我们需要特判$A_i$和$A_j$都等于0的情况，可以计算得出此时三元组的个数恰好为序列中所有在$A_j$右边的元素的个数。也就是$n - j$。整个算法的复杂度为$\mathcal{O}(n^2\log n)$

Problem B. Combining Classes

这道题，是给你$N$个$[L_i, R_i]$连续区间组成的分数，然后有$Q$个查询，问这些区间中所有数字组成的序列的第$K_i$大的分数是多少，其中$N$和$Q$的范围都在$5*10^5$级别。

题解的方法是离散化+线段树区间维护，似乎有一些麻烦。实际上可以直接将区间拆成$2N$个点，然后从大到小排序。接下来就是处理区间端点的问题了，再遍历断点的过程中，我们需要一个变量$cur$用于记录当前分数有多少个人同分，$sum$记录目前总共排好了多少个人，这样在遍历的过程中不断的将$K_i$和$sum$进行比较就可以了。另外需要注意的是，在遍历过程中如果端点的发生了跳跃，我们需要直接算出$K_i$对应的分数，方法就是计算$sum$与$K_i$的差值，然后整除$cur$即可。整个算法中，排序复杂度是$\mathcal{O}(N\log N+Q\log Q)$，遍历的复杂度是$\mathcal{O}(N+Q)$