我上当了.
$path$
枚举出发点 $S$ ,建出以 $S$ 为起点的最短路图,即只保留 $dis(u)+val(i)=dis(v)$ 的边 $i$ .
在最短路图上 $dp$ ,拓扑排序后求出 $f(i)$ 表示 $S\to i$ 的路径条数, $g(i)$ 表示以 $i$ 为起点的路径条数.
那么对于在最短路图上的一条边 $u\to v$ ,以 $S$ 为起点时的所有贡献为 $f(u)\cdot g(v)$ .
时间复杂度 $O(nm\log n)$ .
$seq$
典故 ,来自电子神大的 $OJ$.
由于题面没说清楚,就强行规定 $j>i$ ,把数据修了.
就是要找到右边第一个严格大于 $a_x$ 的位置 $y$ ,那么 $[x+1,y-1]$ 这一段都可以作为答案,可以在线段树上二分.
然后加上从 $y$ 开始,最长单调不下降子序列的长度,这可以分块.
分成 $\sqrt n$ 个块后,维护每一块内部的不下降子序列和块边界处的不下降子序列.
询问时对整块二分,边角暴力.
然而直接 $O(n^2)$ 暴力可以过 $80\sim 100$ 分?
我上当了,写了个线段树 + 定期重构,比暴力的分还少一些,而且我发现去掉重构之后还是差不多慢.
$area$
求圆环的面积并, $n\le 1000$ .
留坑.
我上当了,写了个撒点,精度太垃圾了,甚至要开 $0$ 位小数才能过前两个点.