文章目录

发现宝藏【考生须知】试题 A: 排列字母试题 B: 灭鼠先锋试题 C: 质因数个数试题 D: 数位排序试题 E: 蜂巢试题

F

:

\mathrm{F}:

F: 爬树的甲壳虫试题 G: 重新排序试题

H

\mathrm{H}

H : 技能升级试题 I: 最优清零方案试题

J

:

\mathrm{J}:

J: 推导部分和

发现宝藏

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。【宝藏入口】。

【考生须知】

考试开始后, 选手首先下载题目, 并使用考场现场公布的解压密码解压试题。

考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案, 被浏览的答案允许拷贝。时间截止后，将无法继续提交或浏览答案。

对同一题目, 选手可多次提交答案, 以最后一次提交的答案为准。

选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它方式提交的答案无效。

试题包含 “结果填空” 和 “程序设计” 两种题型。

结果填空题: 要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。把结果填空的答案直接通过网页提交即可, 不要书写多余的内容。

程序设计题: 要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果才有机会得分。

注意: 在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。选手的程序必须是通用的, 不能只对试卷中给定的数据有效。

所有源码必须在同一文件中。调试通过后，拷贝提交。

注意: 不要使用 package 语句。

注意：选手代码的主类名必须为: Main, 否则会被判为无效代码。

注意: 如果程序中引用了类库, 在提交时必须将 import 语句与程序的其他部分同时提交。只允许使用 Java 自带的类库。

试题 A: 排列字母

本题总分: 5 分

【问题描述】

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

例如, LANQIAO 排列后为 AAILNOQ。

又如, GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY

请问对于以下字符串, 排列之后字符串是什么?

WHERETHEREISAWILLTHEREISAWAY

【答案提交】

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串, 在提交答案时只填写这个字符串, 填写多余的内容将无法得分。

试题 B: 灭鼠先锋

本题总分: 5 分

【问题描述】

灭鼠先锋是一个老少咸宜的棋盘小游戏, 由两人参与, 轮流操作。

灭鼠先锋的棋盘有各种规格, 本题中游戏在两行四列的棋盘上进行。游戏的规则为: 两人轮流操作, 每次可选择在棋盘的一个空位上放置一个棋子, 或在同一行的连续两个空位上各放置一个棋子, 放下棋子后使棋盘放满的一方输掉游戏。

小蓝和小乔一起玩游戏, 小蓝先手, 小乔后手。小蓝可以放置棋子的方法很多, 通过旋转和翻转可以对应如下四种情况:

其中 0 表示棋盘上的一个方格为空，

x

\mathrm{x}

x 表示该方格已经放置了棋子。

请问, 对于以上四种情况, 如果小蓝和小乔都是按照对自己最优的策略来玩游戏, 小蓝是否能获胜。如果获胜, 请用

V

\mathrm{V}

V 表示, 否则用

L

\mathrm{L}

L 表示。请将四种情况的胜负结果挍顺序连接在一起提交。

【答案提交】

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个长度为 4 的由大写字母

V

\mathrm{V}

V 和

L

\mathrm{L}

L 组成的字符串, 如 VVLL, 在提交答案时只填写这个字符串, 填写多余的内容将无法得分。

试题 C: 质因数个数

时间限制:

5.0

s

5.0 \mathrm{~s}

5.0 s 内存限制:

512.0

M

B

512.0 \mathrm{MB}

512.0MB 本题总分: 10 分

【问题描述】

给定正整数

n

n

n, 请问有多少个质数是

n

n

n 的约数。

【输入格式】

输入的第一行包含一个整数

n

n

n 。

【输出格式】

输出一个整数, 表示

n

n

n 的质数约数个数。

【样例输入】

396

\begin{array}{llllll}396\end{array}

396​

【样例输出】

3

\begin{array}{llllll}3\end{array}

3​

【样例说明】

396 有

2

,

3

,

11

2,3,11

2,3,11 三个质数约数。

【评测用例规模与约定】

对于

30

%

30 \%

30% 的评测用例,

1

≤

n

≤

10000

1 \leq n \leq 10000

1≤n≤10000 。

对于

60

%

60 \%

60% 的评测用例,

1

≤

n

≤

1

0

9

1 \leq n \leq 10^{9}

1≤n≤109 。

对于所有评测用例,

1

≤

n

≤

1

0

16

1 \leq n \leq 10^{16}

1≤n≤1016 。

试题 D: 数位排序

时间限制:

1.0

s

1.0 \mathrm{~s}

1.0 s 内存限制:

512.0

M

B

512.0 \mathrm{MB}

512.0MB 本题总分： 10 分

【问题描述】

小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时,将数值小的排在前面。

例如, 2022 排在 409 前面, 因为 2022 的数位之和是 6 , 小于 409 的数位之和 13 。

又如, 6 排在 2022 前面, 因为它们的数位之和相同, 而 6 小于 2022 。

给定正整数

n

,

m

n, m

n,m, 请问对 1 到

n

n

n 采用这种方法排序时，排在第

m

m

m 个的元素是多少?

【输入格式】

输入第一行包含一个正整数

n

n

n 。

第二行包含一个正整数

m

m

m 。

【输出格式】

输出一行包含一个整数, 表示答案。

【样例输入】

13

\begin{array}{llllll}13\end{array}

13​

5

\begin{array}{llllll}5\end{array}

5​

【样例输出】

3

\begin{array}{llllll}3\end{array}

3​

【样例说明】

1 到 13 的排序为:

1

,

10

,

2

,

11

,

3

,

12

,

4

,

13

,

5

,

6

,

7

,

8

,

9

1,10,2,11,3,12,4,13,5,6,7,8,9

1,10,2,11,3,12,4,13,5,6,7,8,9 。第 5 个数为 3 。

【评测用例规模与约定】

对于

30

%

30 \%

30% 的评测用例,

1

≤

m

≤

n

≤

300

1 \leq m \leq n \leq 300

1≤m≤n≤300 。

对于

50

%

50 \%

50% 的评测用例，

1

≤

m

≤

n

≤

1000

1 \leq m \leq n \leq 1000

1≤m≤n≤1000 。

对于所有评测用例，

1

≤

m

≤

n

≤

1

0

6

1 \leq m \leq n \leq 10^{6}

1≤m≤n≤106 。

试题 E: 蜂巢

时间限制:

1.0

s

1.0 \mathrm{~s}

1.0 s 内存限制:

512.0

M

B

512.0 \mathrm{MB}

512.0MB 本题总分: 15 分

【问题描述】

蜂巢由大量的六边形拼接而成, 定义蜂巢中的方向为: 0 表示正西方向, 1 表示西偏北

6

0

∘

,

2

60^{\circ}, 2

60∘,2 表示东偏北

6

0

∘

,

3

60^{\circ}, 3

60∘,3 表示正东, 4 表示东偏南

6

0

∘

,

5

60^{\circ}, 5

60∘,5 表示西偏南

6

0

∘

60^{\circ}

60∘ 。

对于给定的一点

O

O

O, 我们以

O

O

O 为原点定义坐标系, 如果一个点

A

A

A 由

O

O

O 点先向

d

d

d 方向走

p

p

p 步再向

(

d

+

2

)

m

o

d

6

(d+2) \bmod 6

(d+2)mod6 方向 (

d

d

d 的顺时针

12

0

∘

120^{\circ}

120∘ 方向) 走

q

q

q 步到达, 则这个点的坐标定义为

(

d

,

p

,

q

)

(d, p, q)

(d,p,q) 。在蜂窝中, 一个点的坐标可能有多种。

下图给出了点

B

(

0

,

5

,

3

)

B(0,5,3)

B(0,5,3) 和点

C

(

2

,

3

,

2

)

C(2,3,2)

C(2,3,2) 的示意。

给定点

(

d

1

,

p

1

,

q

1

)

\left(d_{1}, p_{1}, q_{1}\right)

(d1​,p1​,q1​) 和点

(

d

2

,

p

2

,

q

2

)

\left(d_{2}, p_{2}, q_{2}\right)

(d2​,p2​,q2​), 请问他们之间最少走多少步可以到达?

【输入格式】

输入一行包含 6 个整数

d

1

,

p

1

,

q

1

,

d

2

,

p

2

,

q

2

d_{1}, p_{1}, q_{1}, d_{2}, p_{2}, q_{2}

d1​,p1​,q1​,d2​,p2​,q2​ 表示两个点的坐标, 相邻两个整数之间使用一个空格分隔。

【输出格式】

输出一行包含一个整数表示两点之间最少走多少步可以到达。

【样例输入】

0

5

3

2

3

2

\begin{array}{llllll}0 & 5 & 3 & 2 & 3 & 2\end{array}

0​5​3​2​3​2​

【样例输出】

7

\begin{array}{llllll}7\end{array}

7​

【评测用例规模与约定】

对于

25

%

25 \%

25% 的评测用例,

p

1

,

p

2

≤

1

0

3

p_{1}, p_{2} \leq 10^{3}

p1​,p2​≤103;

对于

50

%

50 \%

50% 的评测用例,

p

1

,

p

2

≤

1

0

5

p_{1}, p_{2} \leq 10^{5}

p1​,p2​≤105;

对于

75

%

75 \%

75% 的评测用例,

p

1

,

p

2

≤

1

0

7

p_{1}, p_{2} \leq 10^{7}

p1​,p2​≤107;

对于所有评测用例,

0

≤

d

1

,

d

2

≤

5

,

0

≤

q

1

<

p

1

≤

1

0

9

,

0

≤

q

2

<

p

2

≤

1

0

9

0 \leq d_{1}, d_{2} \leq 5,0 \leq q_{1}<p_{1} \leq 10^{9}, 0 \leq q_{2}<p_{2} \leq 10^{9}

0≤d1​,d2​≤5,0≤q1​<p1​≤109,0≤q2​<p2​≤109 。

试题

F

:

\mathrm{F}:

F: 爬树的甲壳虫

时间限制:

1.0

s

1.0 \mathrm{~s}

1.0 s 内存限制:

512.0

M

B

512.0 \mathrm{MB}

512.0MB 本题总分: 15 分

【问题描述】

有一只甲壳虫想要爬上一颗高度为

n

n

n 的树, 它一开始位于树根, 高度为 0 ,当它尝试从高度

i

−

1

i-1

i−1 爬到高度为

i

i

i 的位置时有

P

i

P_{i}

Pi​ 的概率会掉回树根, 求它从树根爬到树顶时，经过的时间的期望值是多少。

【输入格式】

输入第一行包含一个整数

n

n

n 表示树的高度。

接下来

n

n

n 行每行包含两个整数

x

i

,

y

i

x_{i}, y_{i}

xi​,yi​, 用一个空格分隔, 表示

P

i

=

x

i

y

i

P_{i}=\frac{x_{i}}{y_{i}}

Pi​=yi​xi​​ 。

【输出格式】

输出一行包含一个整数表示答案, 答案是一个有理数, 请输出答案对质数 998244353 取模的结果。其中有理数

a

b

\frac{a}{b}

ba​ 对质数

P

P

P 取模的结果是整数

c

c

c 满足

0

≤

c

<

P

0 \leq c<P

0≤c<P 且

c

⋅

b

≡

a

(

m

o

d

P

)

c \cdot b \equiv a(\bmod P)

c⋅b≡a(modP) 。

【样例输入 1】

1

\begin{array}{llllll}1\end{array}

1​

1

2

\begin{array}{llllll}1&2\end{array}

1​2​

【样例输出 1】

2

\begin{array}{llllll}2\end{array}

2​

【样例输入 2】

3

\begin{array}{llllll}3\end{array}

3​

1

2

\begin{array}{llllll}1&2\end{array}

1​2​

3

5

\begin{array}{llllll}3&5\end{array}

3​5​

7

11

\begin{array}{llllll}7&11\end{array}

7​11​

【样例输出 2】

623902744

\begin{array}{llllll}623902744\end{array}

623902744​

【评测用例规模与约定】

对于

20

%

20 \%

20% 的评测用例,

n

≤

2

,

1

≤

x

i

<

y

i

≤

20

n \leq 2,1 \leq x_{i}<y_{i} \leq 20

n≤2,1≤xi​<yi​≤20 ，

对于

50

%

50 \%

50% 的评测用例,

n

≤

500

,

1

≤

x

i

<

y

i

≤

200

n \leq 500,1 \leq x_{i}<y_{i} \leq 200

n≤500,1≤xi​<yi​≤200 ；

对于所有评测用例,

1

≤

n

≤

100000

,

1

≤

x

i

<

y

i

≤

1

0

9

1 \leq n \leq 100000,1 \leq x_{i}<y_{i} \leq 10^{9}

1≤n≤100000,1≤xi​<yi​≤109 。

试题 G: 重新排序

时间限制:

1.0

s

1.0 \mathrm{~s}

1.0 s 内存限制:

512.0

M

B

512.0 \mathrm{MB}

512.0MB 本题总分: 20 分

【问题描述】

给定一个数组

A

A

A 和一些查询

L

i

,

R

i

L_{i}, R_{i}

Li​,Ri​, 求数组中第

L

i

L_{i}

Li​ 至第

R

i

R_{i}

Ri​ 个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?

【输入格式】

输入第一行包含一个整数

n

n

n 。

第二行包含

n

n

n 个整数

A

1

,

A

2

,

⋯

,

A

n

A_{1}, A_{2}, \cdots, A_{n}

A1​,A2​,⋯,An​, 相邻两个整数之间用一个空格分隔。

第三行包含一个整数

m

m

m 表示查论的数目。

接下来

m

m

m 行, 每行包含两个整数

L

i

、

R

i

L_{i} 、 R_{i}

Li​、Ri​, 相邻两个整数之间用一个空格分谝。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

5

\begin{array}{lllll}5\end{array}

5​

1

2

3

4

5

\begin{array}{lllll}1 & 2 & 3 & 4 & 5\end{array}

1​2​3​4​5​

2

\begin{array}{lllll}2\end{array}

2​

1

3

\begin{array}{lllll}1&3\end{array}

1​3​

2

5

\begin{array}{lllll}2&5\end{array}

2​5​

【样例输出】

4

\begin{array}{lllll}4\end{array}

4​

【样例说明】

原来的和为

6

+

14

=

20

6+14=20

6+14=20, 重新排列为

(

1

,

4

,

5

,

2

,

3

)

(1,4,5,2,3)

(1,4,5,2,3) 后和为

10

+

14

=

24

10+14=24

10+14=24, 增加了 4 。

【评测用例规模与约定】

对于

30

%

30 \%

30% 的评测用例,

n

,

m

≤

50

n, m \leq 50

n,m≤50 ；

对于

50

%

50 \%

50% 的评测用例,

n

,

m

≤

500

n, m \leq 500

n,m≤500 ；

对于

70

%

70 \%

70% 的评测用例,

n

,

m

≤

5000

n, m \leq 5000

n,m≤5000 ，

对于所有评测用例,

1

≤

n

,

m

≤

1

0

5

,

1

≤

A

i

≤

1

0

6

,

1

≤

L

i

≤

R

i

≤

1

0

6

1 \leq n, m \leq 10^{5}, 1 \leq A_{i} \leq 10^{6}, 1 \leq L_{i} \leq R_{i} \leq 10^{6}

1≤n,m≤105,1≤Ai​≤106,1≤Li​≤Ri​≤106 。

试题

H

\mathrm{H}

H : 技能升级

时间限制:

1.0

s

1.0 \mathrm{~s}

1.0 s 内存限制:

512.0

M

B

512.0 \mathrm{MB}

512.0MB 本题总分: 20 分

【问题描述】

小蓝最近正在玩一款 RPG 游戏。他的角色一共有

N

N

N 个可以加攻击力的技能。其中第

i

i

i 个技能首次升级可以提升

A

i

A_{i}

Ai​ 点攻击力, 以后每次升级增加的点数都会减少

B

i

B_{i}

Bi​ 。

⌈

A

i

B

i

⌉

\left\lceil\frac{A_i}{B_i}\right\rceil

⌈Bi​Ai​​⌉ (上取整) 次之后, 再升级该技能将不会改变攻击力。

现在小蓝可以总计升级

M

M

M 次技能, 他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力?

【输入格式】

输入第一行包含两个整数

N

N

N 和

M

M

M 。

以下

N

N

N 行每行包含两个整数

A

i

A_{i}

Ai​ 和

B

i

B_{i}

Bi​ 。

【输出格式】

输出一行包含一个整数表示答案。

【样例输入】

3

6

\begin{array}{lllll}3&6\end{array}

3​6​

10

5

\begin{array}{lllll}10&5\end{array}

10​5​

9

2

\begin{array}{lllll}9&2\end{array}

9​2​

8

1

\begin{array}{lllll}8&1\end{array}

8​1​

【样例输出】

4

7

\begin{array}{lllll}4&7\end{array}

4​7​

【评测用例规模与约定】

对于

40

%

40 \%

40% 的评测用例,

1

≤

N

,

M

≤

1000

1 \leq N, M \leq 1000

1≤N,M≤1000 ，

对于

60

%

60 \%

60% 的评测用例,

1

≤

N

≤

1

0

4

,

1

≤

M

≤

1

0

7

1 \leq N \leq 10^{4}, 1 \leq M \leq 10^{7}

1≤N≤104,1≤M≤107 ；

对于所有评测用例,

1

≤

N

≤

1

0

5

,

1

≤

M

≤

2

×

1

0

9

,

1

≤

A

i

,

B

i

≤

1

0

6

1 \leq N \leq 10^{5}, 1 \leq M \leq 2 \times 10^{9}, 1 \leq A_{i}, B_{i} \leq 10^{6}

1≤N≤105,1≤M≤2×109,1≤Ai​,Bi​≤106 。

试题 I: 最优清零方案

时间限制:

3.0

s

3.0 \mathrm{~s}

3.0 s 内存限制:

512.0

M

B

512.0 \mathrm{MB}

512.0MB 本题总分: 25 分

【问题描述】

给定一个长度为

N

N

N 的数列

A

1

,

A

2

,

⋯

,

A

N

A_{1}, A_{2}, \cdots, A_{N}

A1​,A2​,⋯,AN​ 。现在小蓝想通过若干次操作将这个数列中每个数字清零。

每次操作小蓝可以选择以下两种之一:

选择一个大于 0 的整数, 将它减去 1 :选择连续

K

K

K 个大于 0 的整数, 将它们各减去 1 。

小蓝最少经过几次操作可以将整个数列清零?

【输入格式】

输入第一行包含两个整数

N

N

N 和

K

K

K 。

第二行包含

N

N

N 个整数

A

1

,

A

2

,

⋯

,

A

N

A_{1}, A_{2}, \cdots, A_{N}

A1​,A2​,⋯,AN​ 。

【输出格式】

输出一个整数表示答案。

【样例输入】

4

2

\begin{array}{lllll}4&2\end{array}

4​2​

1

2

3

4

\begin{array}{llll}1 & 2 & 3 & 4\end{array}

1​2​3​4​

【样例输出】

6

\begin{array}{lllll}6\end{array}

6​

【评测用例规模与约定】

对于

20

%

20 \%

20% 的评测用例，

1

≤

K

≤

N

≤

10

1 \leq K \leq N \leq 10

1≤K≤N≤10 。

对于

40

%

40 \%

40% 的评测用例,

1

≤

K

≤

N

≤

100

1 \leq K \leq N \leq 100

1≤K≤N≤100 。

对于

50

%

50 \%

50% 的评测用例,

1

≤

K

≤

N

≤

1000

1 \leq K \leq N \leq 1000

1≤K≤N≤1000 。

对于

60

%

60 \%

60% 的评测用例,

1

≤

K

≤

N

≤

10000

1 \leq K \leq N \leq 10000

1≤K≤N≤10000 。

对于

70

%

70 \%

70% 的评测用例,

1

≤

K

≤

N

≤

100000

1 \leq K \leq N \leq 100000

1≤K≤N≤100000 。

对于所有评测用例,

1

≤

K

≤

N

≤

1000000

,

0

≤

A

i

≤

1000000

1 \leq K \leq N \leq 1000000,0 \leq A_{i} \leq 1000000

1≤K≤N≤1000000,0≤Ai​≤1000000 。

试题

J

:

\mathrm{J}:

J: 推导部分和

时间限制:

1.0

s

1.0 \mathrm{~s}

1.0 s 内存限制:

512.0

M

B

512.0 \mathrm{MB}

512.0MB 本题总分: 25 分

【问题描述】

对于一个长度为

N

N

N 的整数数列

A

1

,

A

2

,

⋯

A

N

A_{1}, A_{2}, \cdots A_{N}

A1​,A2​,⋯AN​, 小蓝想知道下标

l

l

l 到

r

r

r 的部分和

∑

i

=

l

r

=

A

l

+

A

l

+

1

+

⋯

+

A

r

\sum_{i=l}^{r}=A_{l}+A_{l+1}+\cdots+A_{r}

∑i=lr​=Al​+Al+1​+⋯+Ar​ 是多少?

然而, 小蓝并不知道数列中每个数的值是多少, 他只知道它的

M

M

M 个部分和的值。其中第

i

i

i 个部分和是下标

l

i

l_{i}

li​ 到

r

i

r_{i}

ri​ 的部分和

∑

j

=

l

i

r

i

=

A

l

i

+

A

l

i

+

1

+

⋯

+

A

r

i

\sum_{j=l_{i}}^{r_{i}}=A_{l_{i}}+A_{l_{i}+1}+\cdots+A_{r_{i}}

∑j=li​ri​​=Ali​​+Ali​+1​+⋯+Ari​​,值是

S

i

S_{i}

Si​ 。

【输入格式】

第一行包含 3 个整数

N

、

M

N 、 M

N、M 和

Q

Q

Q 。分别代表数组长度、已知的部分和数量和询问的部分和数量。

接下来

M

M

M 行, 每行包含 3 个整数

l

i

,

r

i

,

S

i

l_{i}, r_{i}, S_{i}

li​,ri​,Si​ 。

接下来

Q

Q

Q 行, 每行包含 2 个整数

l

l

l 和

r

r

r, 代表一个小蓝想知道的部分和。

【输出格式】

对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 UNKNOWN。

【样例输入】

5

3

3

\begin{array}{lll}5 & 3 & 3 \end{array}

5​3​3​

1

5

15

\begin{array}{lll}1 & 5 & 15\end{array}

1​5​15​

4

5

9

\begin{array}{lll}4 & 5 & 9\end{array}

4​5​9​

2

3

5

\begin{array}{lll}2& 3& 5\end{array}

2​3​5​

1

5

\begin{array}{lll}1& 5 \end{array}

1​5​

1

3

\begin{array}{lll}1& 3\end{array}

1​3​

1

2

\begin{array}{lll}1&2\end{array}

1​2​

【样例输出】

1

5

\begin{array}{lll}1& 5\end{array}

1​5​

6

\begin{array}{lll}6\end{array}

6​

U

N

K

N

O

W

N

\begin{array}{lll}UNKNOWN\end{array}

UNKNOWN​

【评测用例规模与约定】

对于

10

%

10 \%

10% 的评测用例,

1

≤

N

,

M

,

Q

≤

10

,

−

100

≤

S

i

≤

100

1 \leq N, M, Q \leq 10,-100 \leq S_{i} \leq 100

1≤N,M,Q≤10,−100≤Si​≤100 。

对于

20

%

20 \%

20% 的评测用例,

1

≤

N

,

M

,

Q

≤

20

,

−

1000

≤

S

i

≤

1000

1 \leq N, M, Q \leq 20,-1000 \leq S_{i} \leq 1000

1≤N,M,Q≤20,−1000≤Si​≤1000 。

对于

30

%

30 \%

30% 的评测用例,

1

≤

N

,

M

,

Q

≤

50

,

−

10000

≤

S

i

≤

10000

1 \leq N, M, Q \leq 50,-10000 \leq S_{i} \leq 10000

1≤N,M,Q≤50,−10000≤Si​≤10000 。

对于

40

%

40 \%

40% 的评测用例,

1

≤

N

,

M

,

Q

≤

1000

,

−

1

0

6

≤

S

i

≤

1

0

6

1 \leq N, M, Q \leq 1000,-10^{6} \leq S_{i} \leq 10^{6}

1≤N,M,Q≤1000,−106≤Si​≤106 。

对于

60

%

60 \%

60% 的评测用例,

1

≤

N

,

M

,

Q

≤

10000

,

−

1

0

9

≤

S

i

≤

1

0

9

1 \leq N, M, Q \leq 10000,-10^{9} \leq S_{i} \leq 10^{9}

1≤N,M,Q≤10000,−109≤Si​≤109 。

对于所有评测用例,

1

≤

N

,

M

,

Q

≤

1

0

5

,

−

1

0

12

≤

S

i

≤

1

0

12

,

1

≤

l

i

≤

r

i

≤

N

1 \leq N, M, Q \leq 10^{5},-10^{12} \leq S_{i} \leq 10^{12}, 1 \leq l_{i} \leq r_{i} \leq N

1≤N,M,Q≤105,−1012≤Si​≤1012,1≤li​≤ri​≤N,

1

≤

l

≤

r

≤

N

1 \leq l \leq r \leq N

1≤l≤r≤N 。数据保证没有矛盾。