花车巡游

题目描述

嘉年华的花车巡游正在展示精心编排的队列变换！

最初，所有 N辆花车排成一行，花车 i 位于第 i 位。变换程序由 K 个位置对 (a1,b1),(a2,b2),…,(aK,bK) 描述。表演过程中：

· 第 1 分钟：位置 a1 与 b1 的花车交换位置

· 第 2 分钟：位置 a2 与 b2 的花车交换位置

· ……

· 第 K 分钟：位置 aK 与 bK 的花车交换位置

· 第 K+1 分钟：重新从 (a1,b1) 开始交换（即位置 a1 与 b1 交换）

· 第 K+2 分钟：位置 a2 与 b2 交换

· 如此无限循环……

请计算每辆花车在整个表演过程中能到达的不同位置数量。

输入格式

第一行输入 N,K。

接下来 K 行每行包含 ai,bi（1≤ai<bi≤N）。

输出格式

输出 N行，第 i行为花车 i能到达的不同位置数量。

输入样例

5 4
1 3
1 2
2 3
2 4

输出样例

4
4
3
4
1

说明提示

样例解释

· 花车 1 可到达位置 {1,2,3,4}

· 花车 2 可到达位置 {1,2,3,4}

· 花车 3 可到达位置 {1,2,3}

· 花车 4 可到达位置 {1,2,3,4}

· 花车 5 始终在位置 5（未移动）

【数据范围】

1≤K≤2×105

2≤N≤105

限制

时间限制：1000ms

内存限制：256MiB

数字之和

题目描述

给定一个数字字符串 n，定义一次操作为：移除字符串中一个非空子串，并将剩余部分拼接形成新数字。

求所有可能操作方案生成的新数字之和，结果对 109+7取模。

输入格式

一行字符串 n

输出格式

一个整数，表示所有方案生成数字之和取模后的结果。

输入样例#1

1003

输出样例#1

339

输入样例#2

123

输出样例#2

52

说明提示

【数据范围】

1≤∣n∣≤105,| n |表示字符串长度。

限制

时间限制：1000ms

内存限制：256MiB

公平

题目描述

有多干所精英学院和 N 名天才学员（编号 1 到 N）。每名学员 i拥有能力值 Ai 和初始所属学院 Bi。

联盟定期进行学员调院操作（共 Q 次）：第 j次操作将学员 Cj 调到学院 Dj。

联盟公平指数定义为：

对每所至少有一名学员的学院，取该学院最高能力值；再取这些最高能力值中的最小值。

请计算每次调院操作后的联盟公平指数。

输入格式

· 第一行：N Q

· 接下来 N 行：每行 Ai Bi，表示学员 ii 的能力值和初始学院

· 接下来 Q 行：每行 Cj Dj，表示将学员 Cj 调到学院 Dj

输出格式

· Q 行：每行一个整数，表示每次操作后的公平指数

输入样例#1

6 3

8 1

6 2

9 3

1 1

2 2

1 3

4 3

2 1

1 2

输出样例#1

6

2

6

输入样例#2

2 2

4208 1234

3056 5678

1 2020

2 2020

输出样例#2

3056

4208

说明提示

1≤N,Q≤2×105，1≤N,Q≤2×105

1≤Ai≤109，1≤Ai≤109

1≤Cj≤N，1≤Cj≤N

1≤Bi,Dj≤2×105，1≤Bi,Dj≤2×105

输入均为整数

每次转园操作会改变所属学院

限制

时间限制：1000ms

内存限制：256MiB

给定一棵包含 N个顶点的树。顶点编号为 1 至 N，第 i条边 (1≤i≤N−1) 连接顶点 ai与顶点 bi。

对于树中任意两个顶点 u 和 v（满足 u<v），定义距离 d(u,v)为连接 u 和 v的简单路径上的边的数量。

请计算所有满足 u<v的顶点对 (u,v) 的距离 d(u,v) 的总和。

输入格式

第一行 ，一个整数表示n

接下来的n−1行，每行两个整数ai,bi.

输出格式

输出所有满足 u<v的顶点对 (u,v) 的距离 d(u,v)的总和。

输入样例#1

3
1 2
2 3

输出样例#1

3

输入样例#2

5
1 2
1 3
1 4
1 5

输出样例#2

10

说明提示

【 数据范围 】

2≤N≤105

1≤ai,bi≤N

限制

时间限制：1000ms

内存限制：256MiB