永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。

并查集 (Union-Find Set) 是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图,求最小生成树的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。

算术天才 ⑨ 非常喜欢和等差数列玩耍。

有一天，他给了你一个长度为 $n$ 的序列，其中第 $i$ 个数为 $a[i]$。

他想考考你，每次他会给出询问 $l, r, k$，问区间 $[l, r]$ 内的数从小到大排序后能否形成公差为 $k$ 的等差数列。
当然，他还会不断修改其中的某一项。

为了不被他鄙视，你必须要快速并正确地回答完所有问题。

注意：只有一个数的数列也是等差数列。

共有 $m$ 部电影，编号为 $1 \sim m$，第 $i$ 部电影的好看值为 $w[i]$。

在 $n$ 天之中（从 $1 \sim n$ 编号）每天会放映一部电影，第 $i$ 天放映的是第 $f[i]$ 部。

你可以选择 $l,r(1 \leq l \leq r \leq n)$，并观看第 $l,l+1,\cdots,r$ 天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。

前几天看 ZKW 线段树，ZKW 说用 Trie 式方法可以解决空间问题从而使 ZKW 线段树能当平衡树用，和 wuvin 讨论了一下发现这么做，时间要么只能优化插入，要么只能优化第 $k$ 大。
想了想，感觉可以将 Trie 树，ZKW 线段树，32 叉线段树，以及压位计算结合起来，这样就得到了一个空间消耗比 32 叉线段树小得多，时间效率比 ZKW 线段树快，结构类似 Trie 的神奇数据结构，常数可是比 VEB 小了太多….
实测效率相当高，若用数组实现，空间消耗为值域大小。

听说此题又卡线段树，没事我们还有 ZKW 线段树……
ZKW 线段树在代码长度(不打标记时)和时间上较普通线段树都有较大优势，在 RMQ 甚至会出现喜闻乐见的 $O(\text{ log }n)$ 踩 $O(\text{ log log }n)$ 甚至 $O(1)$ 算法。
这里记录 ZKW 线段树的基本操作以及较为通用的区间操作(非差分而是标记下传)

乘法逆元是数论中重要的内容，也是 OI 中常用到的数论算法之一。

定义

在 $\text{mod p}$ 意义下我们把 $x$ 的乘法逆元写作 $x^{-1}$
$$x \times x^{-1} \equiv 1 \text{ (mod p)}$$

这里重新复习一下扩展欧几里得算法的常见应用。

普通快速幂在面对大量数据或单个够大数据时效率很低，这个时候我们就需要十进制快速幂，而如果模数是 long long 以内的数，我们可以用快速幂思想 $O(\text{log n})$ 完成快速乘，但我们其实可以 $O(1)$ 完成。

补档计划

明日は明日の风が吹く，调整状态，进入新的征程，好好补一些东西…

SCOI 2017 总结

SCOI 2017 结束了，完挂….
在这里还是先祝贺 wuvin 顺利 A 队，ihopenot 顺利翻盘，为 zyqn 默哀…

最短路及其应用

先挖坑…

一个长度为 $ n $ 的大数，用 $ S_1S_2S_3 \ldots S_n $表示，其中 $ S_i $ 表示数的第 $ i $ 位，$ S_1 $ 是数的最高位，告诉你一些限制条件，每个条件表示为四个数 $( l_1, r_1, l_2, r_2 )$，即两个长度相同的区间，表示子串 $ S_{l_1}S_{l_1 + 1}S_{l_1 + 2} \ldots S_{r_1} $ 与 $ S_{l_2}S_{l_2 + 1}S_{l_2 + 2} \ldots S_{r_2} $ 完全相同。

比如 $ n = 6 $ 时，某限制条件 $ (l_1 = 1, r_1 = 3, l_2 = 4, r_2 = 6) $，那么 $ 123123 $,$ 351351 $ 均满足条件，但是 $ 12012 $,$ 131141 $ 不满足条件，前者数的长度不为 $ 6 $，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

奈特公司是一个巨大的情报公司，它有着庞大的情报网络。情报网络中共有 $n$ 名情报员。每名情报员可能有若干名（可能没有）下线，除 $1$ 名大头目外其余 $n - 1$ 名情报员有且仅有 $1$ 名上线。奈特公司纪律森严，每名情报员只能与自己的上,下线联系，同时，情报网络中任意两名情报员一定能够通过情报网络传递情报。

1. 搜集情报：指派 $T$ 号情报员搜集情报
2. 传递情报：将一条情报从 $X$ 号情报员传递给 $Y$ 号情报员

情报员最初处于潜伏阶段，他们是相对安全的，我们认为此时所有情报员的危险值为0；-旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加1点危险值（开始搜集情报的当天危险值仍为0，第2天危险值为1，第3天危险值为2，以此类推）。传递情报并不会使情报员的危险值增加。为了保证传递情报的过程相对安全，每条情报都有一个风险控制值C。余特公司认为，参与传递这条情报的所有情报员中，危险值大于C的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。

作为一个先学工程的蒟蒻 oier，也就只能在卡常上有一些技巧了……

然而我太弱，并没有去成 WC，虽然感觉 T2 卡三级缓存不是应该很好卡吗？

这里总结松爷的一些技巧和记录一些其他技巧及一些实际例子。

有 $K$ 个棋子在一个大小为N×N的棋盘。一开始，它们都在棋盘的顶端，它们起始的位置是 $(1, a_1),(1, a_2),…,(1, a_k)$，它们的目的地是 $(n, b_1), (n, b_2),…,(n, b_k)$。

一个位于 $(r,c)$ 的棋子每一步只能向右走到 $(r, c + 1)$ 或者向下走到 (r + 1, c)$。

我们把 $i$ 棋子从 $(1, a_i)$ 走到 $(n, b_i)$ 的路径记作 $p_i$。

你的任务是计算有多少种方案把 $n$ 个棋子送到目的地，并且对于任意两个不同的棋子 $i,j$，使得路径 $p_i$ 与 $p_j$ 不相交（即没有公共点）。