Description

题目链接：Luogu 4299

在 X 星球上有 $n$ 个国家，每个国家占据着 X 星球的一座城市。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。

X 星球上战乱频发，如果 A 国打败了 B 国，那么 B 国将永远从这个星球消失，而 B 国的国土也将归 A 国管辖。A 国国王为了加强统治，会在 A 国和 B 国之间修建一条公路，即选择原 A 国的某个城市和 B 国某个城市，修建一条连接这两座城市的公路。

同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。

现在告诉你发生在 X 星球的战事，需要你处理 $m$ 条关于国家首都的信息，具体地，有如下 $3$ 种信息需要处理：

• A x y：表示某两个国家发生战乱，战胜国选择了 $x$ 城市和 $y$ 城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。
• Q x：询问当前编号为 $x$ 的城市所在国家的首都。
• Xor：询问当前所有国家首都编号的异或和。

数据范围：$2\le n\le 10^5$，$1\le m\le 2\times 10^5$

Description

题目链接：Luogu 5196

不为 Farmer John 所知的是，Bessie 还热衷于资助艺术创作！最近，她开始研究许多伟大的诗人们，而现在，她想要尝试创作一些属于自己的诗歌了。Bessie 认识 $n$ 个单词，她想要将她们写进她的诗。Bessie 已经计算了她认识的每个单词的长度 $s_i$，以音节为单位，并且她将这些单词划分成了不同的“韵部”，第 $i$ 个单词的韵部为 $c_i$。每个单词仅与属于同一韵部的其他单词押韵。

Bessie 的每首诗由 $m$ 行组成，每一行必须由 $k$ 个音节构成。此外，Bessie 的诗必须遵循某个指定的押韵模式。每行有一个押韵模式，用大写字母 $e_i$ 表示。所有押韵模式等于 $e_i$ 的行必须以同一韵部的单词结尾。不同 $e_i$ 值的行并非必须以不同的韵部的单词结尾。

Bessie 想要知道她可以写出多少首符合限制条件的不同的诗，答案对 $10^9+7$ 取模。

数据范围：$1\le n,k\le 5\times 10^3$，$1\le m\le 10^5$，$1\le s_i\le k$，$1\le c_i\le n$

Description

题目链接：Codeforces 939D

Tolya 和 Valya 各有一条 T 恤，上面分别有一个长度为 $n$，由小写字母组成的字符串 $S$ 和 $T$。你现在要通过变换 $(c_1,c_2)$ 使得这两个字符串变得一样。

具体来说，你每次可以选择一对小写字母 $(c_1,c_2)$ 并将两个字符串中的 $c_1$ 都变成 $c_2$。你需要求出使两个字符串变成一样的最少变换次数，并输出方案。

数据范围：$1\le n\le 10^5$

Description

题目链接：Codeforces 1106E

新年就要到了，Bob 想要收到很多红包！不过收集红包是一件很费时间的事情。

假设从第 $1$ 秒开始共有 $n$ 秒，一共有 $k$ 个红包，其中第 $i$ 个红包可以在第 $s_i$ 到 $t_i$ 秒（包括端点）收集，并且其中有 $w_i$ 元。如果 Bob 选择拿第 $i$ 个红包，他只能在 $s_i$ 到 $t_i$ 中的一个整数时刻收集，并且他在 $d_i$（包括）时刻前不能收集任何红包。保证 $s_i\le t_i\le d_i$。

Bob 是一个贪心的人，他贪心地收集红包——如果他在第 $x$ 秒有红包可以收集，他会选择其中钱最多的那个红包。如果这样的红包也有多个，他会选择其中 $d$ 最大的那个红包。如果仍然有多个选择，Bob 会在其中随便拿一个。

但是，他的女儿 Alice 不想让她的父亲得到太多的钱。她可以在整数时刻干扰 Bob 最多 $m$ 次。如果 Alice 打算在时刻 $x$ 干扰 Bob，那么他不就能在时刻 $x$ 收集红包，然后在时刻 $x+1$ 恢复通常的策略（没有干扰时这一秒的策略），这可能会使得他丢失一些红包。

如果 Alice 采用最优策略，请计算出 Bob 能拿到的最少的钱数。

数据范围：$1\le n,k\le 10^5$，$0\le m\le 200$，$1\le s_i\le t_i\le d_i\le n$，$1\le w_i\le 10^9$

Description

题目链接：Codeforces 242D

Valera 有 $n$ 个计数器标号为 $1$ 到 $n$。他们之间通过 $m$ 条电路连接。每个计数器都有一个按钮。

起初，每个计数器的值都是 $0$。当你按下某个计数器上的按钮后，这个计数器和与他相连的计数器的值都会增加 $1$。

Valera 和 Ignat 之间在玩一个游戏，Ignat 想了一个长度为 $n$ 的序列 $a_i$。Valera 需要选择一些不同的计数器并按下他们的按钮刚好各 $1$ 次（其他的按钮不能按）。如果整个操作之后，存在一个 $i$ 使得计数器 $i$ 上的值等于 $a_i$，那么 Valera 将会输掉游戏，否则他会获胜。

请你帮助 Valera 选择一些计数器使得他能够获胜，如果无法获胜则输出 $-1$。

数据范围：$1\le n,m\le 10^5$，$0\le a_i\le 10^5$

Description

题目链接：Codeforces 1114E

这是一道交互题！

有一个长度为 $n$ 的秘密的序列 $a_i$（不一定是有序的），满足 $0\le a_i\le 10^9$。这个序列有一个特点：升序排列后是一个等差数列。

你可以询问至多 $60$ 次，询问分为以下 $2$ 种类型：

• 询问一个值 $i(1\le i\le n)$。你将得到 $a_i$ 的值。
• 询问一个值 $x(0\le x\le 10^9)$。如果序列中存在严格大于 $x$ 的数字则返回 $1$ 否则返回 $0$。

在询问结束后，你要找出这个序列的最小元素和公差（排列后得到的等差序列的公差）。

数据范围：$2\le n\le 10^6$，$0\le a_i\le 10^9$

Description

题目链接：BZOJ 3669

为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含 $n$ 个节点 $m$ 条边的无向图，节点标号为 $1,2,3,\dots,n$，边标号为 $1,2,3,\dots,m$。初始时小 E 同学在 $1$ 号节点，隐士则住在 $n​$ 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在 $1$ 号节点住着两种守护精灵：$A$ 型守护精灵与 $B​$ 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。

只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 $E_i$ 包含两个权值 $a_i$ 与 $b_i$。若身上携带的 $A$ 型守护精灵个数不少于 $a_i$，且 $B$ 型守护精灵个数不少于 $b_i​$，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小 E 发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 $A$ 型守护精灵的个数与 $B$ 型守护精灵的个数之和。

数据范围：$2\le n\le 5\times 10^4$，$0\le m\le 10^5$，$1\le a_i,b_i\le 5\times 10^4$

Description

题目链接：BZOJ 2120

墨墨购买了一套 $n​$ 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

• Q l r：询问从第 $l$ 支画笔到第 $r$ 支画笔中共有几种不同颜色的画笔。
• R p c：把第 $p$ 支画笔替换为颜色 $c$。

数据范围：$1\le n,m\le 5\times 10^4$，$1\le c\le 10^6​$

Description

题目链接：Luogu 4234

给定一个标号为从 $1$ 到 $n$ 的、有 $m$ 条边的无向图，求边权最大值与最小值的差值最小的生成树。

数据范围：$1\le n\le 5\times 10^4$，$1\le m\le 2\times 10^5$，$1\le w_i\le 10^4$

Description

题目链接：BZOJ 1977

小 C 最近学了很多最小生成树的算法，$\text{Prim}$ 算法、$\text{Kurskal}$ 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 $E_M$，严格次小生成树选择的边集是 $E_S$，那么需要满足（$\text{value}(e)$ 表示边 $e$ 的权值）：$\sum_{e \in E_M}\text{value}(e)<\sum_{e \in E_S}\text{value}(e)$

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

数据范围：$1\le n\le 10^5$，$1\le m,\le 3\times 10^5$，$0\le \text{value}(e)\le 10^9$