光历 2506 年，纷争世初尼卡多利锻斫世百兵，欲取诸支柱泰坦首级。唯有歌耳戈部族追随其行迹，途径特雷托斯城时，歌耳戈徒手击杀为害多年的猛狮。众人逐尼卡多利数年后，终于被其认可，获授天谴之锋；以巨石相砌，层层拱卫这柄锋刃，最终与 2506 年砌成一座移动要塞——此即最初的悬锋之城。歌耳戈即为第一代悬锋之王，后世尊其为「悬锋建城者」、「搦狮之王」。

光历 3870 年自由月，"逐火之旅" 正式开启。

光历 4931 年，两名天外之人降临翁法罗斯。

现在开拓者和丹恒在翁法罗斯遇到了一个奇怪的谜题，给定一个指定的年份区间 $l,r$ ，询问你有多少个年份存在 $4931$ 这段数字。例如 $14931$ 是符合要求的年份，而 $140931$ 是不符合要求的年份。但你无需输出有多少个年份存在 $4931$ ，只需要输出这些年份的和即可。

输入格式

输入一行，包含两个正整数 $l,r$ 。 $(1\le l\le r\le 10^9)$

输出格式

输出一行，为 $l\sim r$ 中所有含有 $4931$ 这段数字的年份的和。

样例输入 1

114514 1919810

样例输出 1

562209021

样例输入 2

1 34725

样例输出 2

T5. 蔡光想成为星铁大师【算法赛】

题目描述

自从那一战以后， $Bronya$ 便接手成为贝罗伯格下层区的领导者。

贝罗伯格下层区错综复杂，可以抽象为 $n$ 个点， $m$ 条边长不一致的无向图。而其中的人民也有三六九等，划分他们的方式很特殊：找得到其中最小生成树的是上等人；找得到其中次小生成树的是中等人；剩余的找得到第三小生成树的人称为下等人。

定义：生成树为经过所有 $n$ 个点，有 $n - 1$ 条边的联通图。最小生成树边权和在所有生成树中最小，次小生成树边权和仅比最小生成树大，第三小生成树的边权和仅比最小生成树和次小生成树大。

显然最小生成树、次小生成树、第三小生成树不一定唯一。但满足

现在， $Bronya$ 要去除旧时代的残党，他找到蔡光想要知道这三等人所找得到的生成树权值和分别是多少，你能帮帮蔡光吗？

样例输入

第一行两个整数 $n, m$ $(2 \leq n \leq 2^{19},n - 1\leq m \leq \min(\frac {n \times (n - 1)}{2}, 2^{20}) \space)$ 。

接下来 $m$ 行，对第 $i + 1$ 行，每行三个整数 $u_i, v_i, w_i$ $(1 \leq u_i < v_i \leq n, 1 \leq w_i \leq 2^{22})$ 。含义如题，数据保证边权两两不同。

样例输出

输出 $1$ 行，包含三个整数 $sum_1, sum_2, sum_3$ ，分别代表上中下等人找得到的生成树权值是多少，或输出 $-1$ 报告不存在这种人。

样例输入 1

样例输出 1

3 4 5

样例输入 2

3 2
1 2 1
2 3 2

样例输出 2

3 -1 -1

T6. 开发模拟宇宙【算法赛】

问题描述

模拟宇宙是由黑塔和其他天才俱乐部的成员（<创生领域大师>阮•梅、<机械贵族>螺丝咕姆、<怪人>斯蒂芬•劳艾德）开发的一个用于研究星神的模拟系统。

现在天才们为了更好的开发模拟宇宙，设计了一款模拟宇宙管理工具 9it。

模拟宇宙中有 $n$ 份文件，初始的第 $i$ 份文件上记录了数字 $a_i$ ，随后天才们会多次更改文件上的数字，我们将每次修改后的整个序列 $a_1..a_n$ 称为一个模拟宇宙版本，9it会记录模拟宇宙的所有历史版本。

9it 支持分支操作，使得所有的历史版本构成了一棵树形结构。初始仅有一条分支（编号为 1），包含一个初始版本。

修改数字操作会在当前分支下产生一个新版本节点，创建分支操作则会在当前分支的最新版本节点下创建两个子版本节点，分别作为原分支和新分支，新分支的初始内容和原分支相同，随后在新分支上进行的修改会独立记录，不再影响原分支的内容。

9it 可以在多个分支间来回切换，修改不同版本的模拟宇宙内容，但如果两个分支在分叉后都对同一个文件进行过修改，则我们称这两条分支不兼容。天才们希望你帮他检查两条分支是否兼容。

具体来说，9it 需要支持以下操作：

upd x y 将当前分支的第 x 项修改为 y。
branch x 移动到分支 x；若编号为 x 的分支不存在，则会先在当前分支下创建分支 x，再移动到 x
query x k 查询分支 x 上的第 k 个文件，你需要输出它上面的数字。
check x y k 检查分支 x 和分支 y 上的第 k 个文件是否兼容，即这两个分支是否同时修改了 k。若兼容则输出 YES，否则输出 NO。

注意：仅在两个分支分开后各自进行的独立修改才会导致不兼容，分叉前进行的修改没有影响；

再注：即使修改内容相同，只要都进行过修改，即视为不兼容。

输入格式

第一行包含两个正整数 $n,m$ ，表示模拟宇宙文件个数和操作次数。 $(1\le n,m \le 10^5)$

第二行包括 $n$ 个正整数 $a_1..a_n$ 。 $(0 <a_i <10^9)$

接下来 $m$ 行，每行表示一个操作，具体格式如上所述。

保证输入合法，保证分支编号 $1\le x \le 10^5$ ，修改内容 $0 <y <10^9$

输出格式

对于所有 query 和 check 操作，做出相应输出。

样例输入

3 8
3 2 5
upd 2 5
branch 2
upd 1 6
query 1 1
check 1 2 1
branch 1
upd 1 4
check 1 2 1

样例输出

3
YES
NO

说明

所有命令执行完后的状态如图所示：

分支 1 和分支 2 在 3,5,5 处分叉，第一次检查时，分支 2 将第一位更改为 6，而分支 1 没有进行更改；第二次检查时，分支 2 将第一位更改为 6，分支 1 将第一位更改为 4，存在冲突。

0607 第 29 场 蓝桥·算法挑战赛

0607 第 29 场蓝桥·算法挑战赛