| rank | solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 79 | 8 | O | Ø | O | . | Ø | O | . | Ø | Ø | O |
A
Solved by Henry and XLor.
二分答案。
用 ST 表，类似于笛卡尔树一样分治，判断是否等价。
B
UpSolved by XLor.
求 $\int_0^\infty \Pi_{i=1}^n {1 \over a_i^2 + x^2} dx$。
乘积式不容易积分，展开成和式分别积分。
C
Solved by Forsaken.
好像乱搞水过去了？
E
UpSolved by Forsaken.
F
Solved by Forsaken.
随机撒点，发现期望比上面积的两倍，约等于 $11$，感受一下很对。
H
UpSolved by Forsaken and XLor.
由期望的线性性，转换为求每个元素在多少个集合内。
求出线性基，线性基的秩为 $r$。
对于不在线性基中的每个元素，余下不在基中的元素可以任意取，并且对应线性基中的唯一一种组合方式。
对于线性基中的元素，如果他是一个唯一的基，则无法取出元素异或出来为 $0$，否则参照上面计算贡献即可。
I
UpSolved by XLor.
给定 $n$ 个二维平面上的点，每个点有权值 $a_i$ 和 $b_i$。
将点集划分为两个集合，满足任意 A 集合的点 $i$ 和 B 集合点 $j$，要么 $x_i < x_j$，要么 $y_i > y_j$。
A 集合的点使用权值 $a_i$，B 集合的点使用权值 $b_i$，要求最大化权值和。
题目即是用一个阶梯型的分段函数将点集划分为两块，A 集合在左上，B 集合在右下，边界上的点属于 B 集合。
线段树维护分界线纵坐标为 $i$ 时的最大权值和 $f(i)$。
从左至右扫描线，对于一个点 $i$，如果他作为分界线的转折点，则需要从前面 $\max_{j=1}^{y_i} f(j)$ 这条分界线转移过来，注意纵坐标由上至下排序。
对于高度大于 $y_i$ 的分界线端点，他一定会取到点 $i$，即区间加上权值 $b_i$。
对于高度小于 $y_i$ 的分界线端点，他一定不会取到点 $i$，即区间权值加上 $a_i$。
J
Solved by XLor.
int128 水过去了。