数数（count） 【题目描述】 Yang ⁡ Yang 和 Bo ⁡ Bo 在无聊时喜欢通过写数字来检验他们俩的默契程度。

假设 Yang ⁡ Yang 写的数是 x x， Bo ⁡ Bo 写的数是 y y。

当 x x 的最高位等于 y y 的个位，且的 y y 最高位等于 x x 的个位时，我们称是一对“默契数”（对于不同的 x x 和 y y， ( x , y ) (x,y) 和 ( y , x ) (y,x) 是不同的）。

现在他们俩想知道，对于所有的 1 ≤ x , y ≤ n 1≤x,y≤n，有多少对默契数呢？

【输入格式】 从文件 c o u n t . i n count.in中读入数据。

一行一个正整数 n。

【输出格式】 输出到文件 c o u n t . o u t count.out中。

一行一个整数表示答案。

【样例 1 1 输入】 11 【样例 1 1 输出】 12 【样例 1 1 解释】 12 12 对默契数为： ( 1 , 1 ) (1,1)， ( 1 , 11 ) (1,11)， ( 2 , 2 ) (2,2)， ( 3 , 3 ) (3,3)， ( 4 , 4 ) (4,4)， ( 5 , 5 ) (5,5)， ( 6 , 6 ) (6,6)， ( 7 , 7 ) (7,7)， ( 8 , 8 ) (8,8)， ( 9 , 9 ) (9,9)， ( 11 , 1 ) (11,1)， ( 11 , 11 ) (11,11)。

【数据范围】 对于 40 % 40% 的数据，保证 n ≤ 10 n≤10。

对于 70 % 70% 的数据，保证 n ≤ 2 × 1 0 3 n≤2×10 3 。

对于 100 % 100% 的数据，保证 1 ≤ n ≤ 2 × 1 0 5 1≤n≤2×10 5 。

音乐（music） 【题目描述】 有一张音乐专辑，它由 n + m n+m 首音乐组成，对于 1 ≤ i ≤ n + m 1≤i≤n+m，若 a i

1 a i ​ =1 表示你喜欢这个音乐，若 a i

0 a i ​ =0 表示你不喜欢这个音乐。

对于序列 a a，定义它的 cobom 值为一个最大的 k k，满足存在一个 1 ≤ i ≤ n + m − k + 1 1≤i≤n+m−k+1，且 a i

a i + 1

a i + 2

. . .

a i + k − 1

1 a i ​ =a i+1 ​ =a i+2 ​ =...=a i+k−1 ​ =1。

现在你已经知道这一张音乐专辑有 n n 首你不喜欢的音乐， m m 首你喜欢的音乐。

你需要回答该如何安排这 n + m n+m 首音乐的顺序，使得 cobom 值最大或最小。

本题使用多组询问。

【输入格式】 从文件 m u s i c . i n music.in中读入数据。

第一行输入一个正整数 t t，表示测试组数。

接下来 t t 行，每行两个非负整数 n , m n,m。

【输出格式】 输出到文件 m u s i c . o u t music.out中。

输出 t t 行，每行两个非负整数，分别表示最大和最小的 cobom 值。

【样例 1 1 输入】 5 5 4 100 50 252 52 3 0 10 10 【样例 1 1 输出】 4 1 50 1 52 1 0 0 10 1 【数据范围】 测试点编号 n , m ≤ n,m≤ 特殊限制 1 ∼ 5 1∼5 8 8 无 6 ∼ 10 6∼10 1 0 6 10 6

11 ∼ 15 11∼15 1 0 18 10 18 保证 m

0 m=0 16 ∼ 20 16∼20 无 对于所有数据，满足 1 ≤ t ≤ 1000 , 0 ≤ n , m ≤ 1 0 18 1≤t≤1000,0≤n,m≤10 18 。

最短路（lcm） 【题目描述】 有很多很多个点，它们的编号从 2 2 开始一直到 1 0 100 10 100 。

对于两个编号为 i , j i,j 的点，从 i i 到 j j，或者从 j j 到 i i 都需要花费 lcm ( i , j ) (i,j) 的时间，其中 lcm ( x , y ) (x,y) 表示 x , y x,y 的最小公倍数，比如 lcm ( 12 , 15 )

60 (12,15)=60。

现在给出 x , y x,y，求从 x x 到 y y 最少需要多少时间。

本题开启多组测试。

【输入格式】 从文件 l c m . i n lcm.in 中读入数据。

第一行输入一个正整数 t t，表示测试组数。

接下来 t t 行，每行两个正整数 x , y x,y，表示一次询问。

【输出格式】 输出到文件 l c m . o u t lcm.out中。

输出 t t 行，每行一个正整数，表示答案。

【样例 1 1 输入】 3 3 4 10 15 2 4 【样例 1 1 输出】 10 25 4 【样例 1 1 解释】 以第一个询问为例，答案是 3 → 2 → 4 3→2→4，时间是 6 + 4

10 6+4=10，可以证明没有比这更优的方案了。

【数据范围】 测试点编号 x , y ≤ x,y≤ 特殊限制 1 ∼ 5 1∼5 10 10 无 6 ∼ 10 6∼10 500 500 11 ∼ 15 11∼15 1 0 7 10 7

x , y x,y 都是质数 16 ∼ 20 16∼20 无 对于所有数据，保证 1 ≤ t ≤ 1000 , 2 ≤ x , y ≤ 1 0 7 1≤t≤1000,2≤x,y≤10 7 。

括号（bracket） 【题目描述】 给出一个长度为 n n 的括号序列 s s。

我们定义一个子序列是合法的，要满足以下条件：

该子序列是一个匹配的括号序列 对于这个匹配，不存在超过一层嵌套的匹配，比如说 ()() 是合法的，但 (()) 不合法，因为它嵌套了两层。 而对于一个子序列，设 m m 为它的长度， i d i id i ​ 表示子序列中第 i i 个字符在 s s 中对应的下标。

子序列 t t 的权值是所有为 ')' 的字符在原序列中出现位置的和减去所有为 '(' 的字符在原序列中出现位置的和，严格来说就是 ∑ i

1 m i d i [ t i

′ ) ′ ] − ∑ i

1 m i d i [ t i

′ ( ′ ] i=1 ∑ m ​ id i ​ [t i ​

′ ) ′ ]− i=1 ∑ m ​ id i ​ [t i ​

′ ( ′ ]

接下来我们有 q q 次修改，每次修改给出 x , c x,c，将 s x s x ​ 的字符改成 c c，保证 c c 是一个 '(' 或 ')' 。

在每次修改后，回答权值最大的子序列的权值，如果此时不存在仍和一个合法子序列，输出 0 0。

【输入格式】 从文件 b r a c k e t . i n bracket.in中读入数据。

第一行给出两个正整数 n , q n,q，表示这个字符序列的长度和询问次数。

接下来一行一个长度为 n n 的字符串 s s，保证 s s 由 '(' 和 ')' 字符组成。

最后 m m 行，每行输入一个正整数和一个字符 x , c x,c，表示一次修改操作。

【输出格式】 输出到文件 b r a c k e t . o u t bracket.out 中。

输出 q q 行，每行一个正整数，第 i i 行的数表示第 i i 次修改后的答案。

本题的输入输出量较大，建议使用较快的输入输出方式。

【样例 1 1 输入】 5 2 ()))) 1 ) 2 ( 【样例 1 1 输出】 0 3 【样例 1 解释】 第一次修改后，括号序列变为 ’ ) ) ) ) ) ’ ’)))))’，选不出任何合法子序列。第二次修改后，括

号序列变为 ’ ) ( ) ) ) ’ ’)()))’，选择下标 2 2 和 5 5 的括号作为当前子序列。

【数据范围】 测试点编号 n , q ≤ n,q≤ 特殊限制 1 ∼ 5 1∼5 8 8 无 6 ∼ 10 6∼10 n ≤ 1 0 6 , q ≤ 5 n≤10 6 ,q≤5 11 ∼ 15 11∼15 1 0 6 10 6 A 16 ∼ 20 16∼20 无 A：保证对于任意时刻，最多只有一个 ')' 字符。

对于所有数据，保证 1 ≤ n , q ≤ 1 0 6 , 1 ≤ x ≤ n 1≤n,q≤10 6 ,1≤x≤n。