DUMBLOG

解析

题目很坑，题中的子段是不能为空的。

其余就是一个比较裸的线段树维护区间最大值，在左右区间是否重合、包含上讨论一下就好了（虽然我调了快一晚上）。

题面

武士藤藤准备击杀地图上的幽灵。

地图为 $n \times m$（行，列）的整点网格图，坐标从左向右从下到上从 $0$ 编号。

开始藤藤可以从地图的任意的左侧进入，最后藤藤将从地图的右侧离开。

藤藤地图上的行进有一些奇妙的性质：

1．藤藤每单位时间会向右移动一单位长度，以尽快从地图上离开。
2．当一只幽灵与藤藤坐标重合，藤藤就会将其击杀。

解析

先说下 Kruskal重构树 是啥。

解析

记录一下每个数前面第一个比它大的和比它小的数的位置，然后从后往前跳。

先把比它大的找到，然后让比它小的在范围内向前跳，跳得越前越好。

每次跳完答案加一。

洛谷题目链接
Acwing题目链接

思路

先预处理出最近和次近的城市，记录下每次循环后所在城市的位置，然后倍增处理。

背景

给定一张带负权边的有向无环图（DAG），$N$ 个点，$M$ 条边，求源点到各点的最短路。

分析

因为有负权边，无法用 dijkstra 直接求最短路。

用 SPFA 又容易被出题人卡成傻子。

考虑到是 DAG，可以使用拓扑排序在 $O\left( N+M \right)$ 时间范围内求出最短路。

已经是22年了捏。

！！！🏮新年好🏮！！！

Dumby_cat 隆重推出 Dumblog 新年款！！！（其实就是变红了。。。）

总之，祝各位来访者新年快乐！！！

加法及乘法原理

加法原理

完成一件事有 $n$ 类方法，每类方法有 $m$ 个不同的方法，那么完成这件事总共就有 $N=m_{1}+m_{2}+…+m_{n}$ 种方法。

题目描述

试求出：

$\left \lceil \left ( \frac{1+\sqrt{5}}{2} \right )^{n} \right \rceil \bmod 998244353$

多测

洛谷P3263

题意描述

给定 $b$、$d$ 和 $n$。

试求出：

$\left \lfloor \left ( \frac{b+\sqrt{d} }{2} \right )^{n} \right \rfloor \bmod{p} $