替换

题目描述

有一个包含 N 个正整数A1​,A2​,⋯,AN​ 的数列 A。接下来将进行 Q 次操作：

在第 ii 次操作中，将数列中所有值为 Bi的元素替换为 Ci。
请针对每次操作（1≤i≤Q），输出操作后数列 A的所有元素之和 Si​。

输入格式

· 第一行，一个整数 N；

· 第二行，N 个整数 A1​,A2​,…,AN​；

· 第三行，一个整数 Q。

· 接下来 Q行，每行两个整数 Bi​,Ci​。

输出格式

输出 Q行，每行一个整数 Si​，表示每次操作后的数列总和。

注意：Si​ 可能超出32 位整数范围。

输入样例#1

4

1 2 3 4

3

1 2

2 4

3 4

输出样例#1

11

15

16

输入样例#2

5

1 2 3 4 5

5

1 2

2 3

3 4

4 5

5 1

输出样例#2

16

18

21

25

5

说明提示

【数据范围】

· 1≤N,Q,Ai​,Bi​,Ci​≤10⁵，

· B_i≠C_i。

限制

时间限制：1000ms

内存限制：256MiB

无法整除的数

题目描述

给定一个长度为 NN的数列 A。
请计算满足以下条件的下标 i（1≤i≤N）的数量：

对于任意 j（1≤j≤N且 i≠j），元素 Ai​ 不能被 Aj​ 整除。

输入格式

· 第一行，一个整数N；

· 第二行，N 个整数表示 A1​,A2​,…,AN​。

输出格式

输出一个整数，表示满足条件的下标数量。

输入样例#1

5

2 3 9 11 19

输出样例#1

4

输入样例#2

10

11 18 45 28 8 19 89 86 2 4

输出样例#2

5

说明提示

【数据范围】

· 所有输入均为整数；

· 1≤N≤2×10⁵；

· 1≤Ai​≤10⁶。

限制

时间限制：1000ms

内存限制：256MiB

咖啡机

题目描述

一台自动咖啡机按以下规则接单：制作一杯咖啡需要
c秒，只有当前订单制作完成后，才能处理下一个订单。如果在制作期间，接到新订单，则做忽略处理。

有 n位顾客下单，其中第 i位顾客的下单时间为第 ti​ 秒，保证所有下单时间均不重复。这台咖啡机最多能完成多少杯订单？

输入格式

· 第一行，两个整数表示 n,c；

· 第二行，nn 个整数表示 t1​,t2​,t3​,…,tn​。

输出格式

这台咖啡机最多能完成多少杯订单。

输入样例#1

6 5

1 3 12 10 8 7

输出样例#1

3

输入样例#2

3 2

0 2 4

输出样例#2

3

输入样例#3

10 3

0 3 4 9 15 12 6 17 19 20

输出样例#3

7

说明提示

【数据范围】

· 1≤n≤100；

· 1≤c≤1000；

· 0≤ti​≤1000。

限制

时间限制：1000ms

内存限制：256MiB

字符数对

题目描述

给定一个由字符 o 和 x 组成的长度为 N的字符串 S。
请计算满足以下所有条件的整数对 (l,r)的数量：

· 1≤l≤r≤N；

· 在字符串 S 的子串S[l..r]（从第 l个字符到第 r个字符）中，同时包含 o 和 x 两种字符。

输入格式

· 第一行，一个整数 N；

· 第二行，一个字符串 S。

输出格式

输出满足条件的整数对的数量。

输入样例#1

4  

oxxo

输出样例#1

5

输入样例#2

7  

xoxooxx

输出样例#2

19

说明提示

· 1≤N≤10⁶；

· S 仅由字符 o 和 x 组成。

限制

时间限制：1000ms

内存限制：256MiB