Personal Blog
也是比较巧妙的一个转换思想。
我们考虑列式：
\[ \sum_{i = 1}^n \sum_{j = i + 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} \]
直接去算或者是按贡献计算都不行，我们考虑转换成这样：
\[ \frac{ \sum_{i = 1}^n \sum_{j = 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} – \sum_{i = 1}^n {2(a_i + b_i) \choose a_i + b_i} }{2} \]
前面那个部分我们可以把点\((-a_i, -b_i)\)放在平面上，然后算一个路径计数的 DP 即可（因为平面大小比较小）。前半部分就是所有第三象限的点走到\((x_i, y_i)\)的路径总数，后半部分直接暴力算即可。
这道题好有意思啊，提醒我在任何时候都要想到这种阈值+\(0/1\)转化的方式。
我们可以先二分出\(c\)位置的值，然后令所有大于等于\(c\)的值变成\(1\)，小于的则变成\(0\)。然后排序的时候发现，其实就是重新组织零一的位置，所以用线段树区间修改就可以搞定了。最后判断\(c\)位是否为\(0/1\)决定要不要继续二分。
假的单调队列哦。
考虑将每个类别元素的下标记好，然后先把每个类别标号最小的放入 multiset，然后对答案进行更新：每次取出最大和最小值做差更新，然后把最小值的下标更新后重新扔进 multiset 中。如果 multiset 中所有的类别都已经枚举完毕，那么直接跳出循环进行输出即可。
首先，强烈推荐阅读这篇文章。（看懂了就不用来了）
Miller-Robin 算法包括两个部分，一个是费马测试，还有一个就是二次探测。这两个东西听上去非常的玄学（的确也是），我来讲清楚，并附上代码。我们现在要进行测试的数是\(p\)。
给定一个平面\((n,m)\)，处理如下操作：