萌萌题，但是看错题。
典典题。
二分平均值 x x x。统计均值小于 x x x 的方案数，每个数减去 x x x 后即统计多少个区间和 < 0 <0 <0。容易发现是个二维偏序问题，归并排序统计即可。
典典题。
n
≤
1500
n \le 1500
n≤1500，
O
(
n
3
)
O(n^3)
O(n3) 可以用 bitset 优化。
记
S
S
S 为
u
,
v
u,v
u,v 均能到达的点集，答案为：
∑
(
u
,
v
)
∈
E
(
deg
(
u
)
−
1
)
×
(
deg
(
v
)
−
1
)
−
∣
S
∣
\sum_{(u,v)\in E} (\deg (u) - 1) \times (\deg(v) - 1)-|S|
(u,v)∈E∑(deg(u)−1)×(deg(v)−1)−∣S∣
哈哈题。
大体思路就是每个点被 bfs 更新的第一次就是最短路。
O ( n 2 + n + m ) O(n^2+n+m) O(n2+n+m)：暴力建边 bfs 即可。
考虑建权值虚点，原图点向对应权值虚点建权值为 1 1 1 边。
O ( 3 20 + n + m ) O(3^{20} + n + m) O(320+n+m)：对于每个 v a l i val_i vali 向其子集虚点建权值为 0 0 0 的边。
O ( 20 × 2 20 + n + m ) O(20\times 2^{20}+n+m) O(20×220+n+m)：为避免重复的访问，对于每个 v a l i val_i vali 向 v a l i val_i vali 去掉一位的权值虚点建权值为 0 0 0 的边。
预估 100 + 100 + 100 + 40 = 340 100+100+100+40=340 100+100+100+40=340，实际 10 + 40 + 100 + 20 = 260 10+40+100+20=260 10+40+100+20=260。A 题目看错，提交期间重新交了一发。B 用 BIT 多次离散化会比归并多点常数，被卡到了 40 40 40。C 没啥好说的。D 建虚点的套路比较难想。挂了 170 170 170 分？