Jumping

更好的阅读体验 CF1550F Jumping Around 提供一个不用动脑子的方法。 首先题目可以看成是求一个点到 \(s\) 的最小瓶颈路，设这个值为 \(v_i\)，自然想到最小生成树，但是边数是 \(\mathcal O(n^2)\) 的，不可接受。 考虑使用 prim，一开始联通块力只有 ......

题面翻译 题目描述 瓦西亚在和忍者玩电脑游戏。在这个关卡，瓦西亚需要操控忍者走出一个很深的峡谷。 峡谷由两面垂直于地面且互相平行的墙组成，它们的高度为\(n\)米。我们将这些墙分成许多\(1\)米长的区域，并从下到上用\(1\)到\(n\)的正整数对它们进行编号。有些地方是安全的，忍者可以爬上去。有 ......

1、首先，假设我们已知一个k，若其符合题意，那么 第一次移动时可达区间为[-k,k]，我们只需判断这个区间和[L1,R1]是否有交区间。然后我们取出这个交区间【left，right】。 接下每次移动，我们都在上一次得到的区间基础上得到新的可移动区间【left-k，right+k】，之后再和【Li，R ......

题目传送门 我是彩笔 二分trigger：存在一个最小值，使得当大于最小值时一定成立，小于最小值时一定不成立 #include<bits/stdc++.h> using namespace std; int n; int l[200005]={0},r[200005]={0}; int ss(int ......

不妨认为 \(n,q\) 同阶。 考虑根号重构。如果没有第 3 种操作的话，我们每 \(\mathcal O(\sqrt n)\) 操作整体更新一次，每个询问只需要考虑块内的修改所在置换环上有多少 \([l,r]\) 内的数。这个是容易 \(\mathcal O(n\sqrt n)\) 做的。 然后 ......

## problem 一只青蛙，他会跳，现在要从 $1$ 跳到 $n$。跳一次有 $m$ 种跳法，假设现在在 $x$，那么第 $i$ 次可以从 $x$ 跳到 $x+d_i$，同时消耗 $p_j$ 的能量。问你有多少种跳的方案使得消耗能量不超过 $k$。$n\leq 10^9,m\leq 10^5,1 ......

[洛谷传送门](https://www.luogu.com.cn/problem/AT_abc221_g "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/abc221/tasks/abc221_g "AtCoder 传送门") 这个数据范围让我们 ......

发现这个 $(x, y)$ 对应的是曼哈顿距离不太好求，那直接逆时针旋转 $45$ 度（其实应该还要伸长 $\sqrt{2}$ 倍，但是可以当做 $d_i$ 也伸长 $\sqrt{2}$ 倍不用去管）转化成切比雪夫距离 $(x - y, x + y)$。 同时对应的 $4$ 个方向在旋转后对应的方向 ......

显然无法用 polylog 的数据结构维护，序列分块也不行，考虑询问分块。每 $B$ 个询问处理一次。 将这个询问中 $2,3$ 操作涉及到的点设为“关键点”，那么容易发现，环上每一段以关键点结尾的链在这块操作的过程中始终保持不变，也就是说我们可以把它们缩在一起。 先预处理出每个块的增量对每组询问的 ......