传统题 3000ms 512MiB

关老师的小游戏

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

关老师是一个办事能力特别强的老师,因此她平时会被安排去做很多事情,很少有休息的时间。这天,关老师难得有空,于是她来到 ACMACM 实验室看望小王,并且和小王玩起了游戏。

游戏规则如下:关老师有 nn 个可以无限装水的桶,它们在刚开始的时候都是空的。关老师会随机给一些水桶加水,这期间也会有其他同学来用水桶的水。关老师会时不时告诉小王某些编号连在一起的水桶x(x1)x(x \ge 1) 毫升水,或者告诉小王某个水桶现在有 y(y1)y(y \ge 1) 毫升水。小王需要做的就是记下当前每个水桶里有多少水,关老师会随机抽查让小王说出一些水桶一共有多少毫升水,或者让小王说出某个水桶有多少毫升水。

输入格式

第一行输入一个数 n(1n2×105)n(1 \le n \le 2 \times 10^5),表示关老师一共有 nn 个空的水桶,从 1n1 \sim n 分别为第 11 个桶,第 22 个桶 \dotsnn 个桶;
第二行输入一个数 t(1t2×106)t(1 \le t \le 2 \times 10^6),表示接下来输入 tt 行,每行第一个数表示你要进行的是第几个操作,这些操作分别是:

  • 11 aa bb x1x_1 x2x_21abn1 \le a \le b \le n1x1x21061 \le x_1 \le x_2 \le 10^6,以空格分隔)表示要先求出 x1x_1x2x_2(包括 x1x_1x2x_2)之间素数的数量 xx,然后重置第 aa 个桶到第 bb 个桶(包括第 aa 个桶和第 bb 个桶)之间的所有桶xx 毫升水,关老师保证 x1x \ge 1
  • 22 cc y1y_1 y2y_21cn1 \le c \le n1y1y21061 \le y_1 \le y_2 \le 10^6,以空格分隔)表示要先求出 y1y_1y2y_2(包括 y1y_1y2y_2)之间素数的数量 yy,然后重置第 cc 个桶有 yy 毫升水,关老师保证 y1y \ge 1
  • 33 dd ee1den1 \le d \le e \le n,以空格分隔)表示关老师询问小王第 dd 个桶到第 ee 个桶(包括第 dd 个桶和第 ee 个桶)现在一共有多少毫升水;
  • 44 ff1fn1 \le f \le n,以空格分隔)表示关老师询问小王第 ff 个桶现在有多少毫升水

输出格式

对于关老师每次的询问,输出一个整数表示小王的回答,每个回答占据一行。

样例

5
4
2 3 5 20
4 3
1 1 5 24 33
3 1 5
6
10

样例解释

一共有 55 个桶,44 次操作:

  • 第一次操作,552020 之间一共有 66 个素数,因此第 33 个桶里的水当前有 66 毫升;
  • 第二次操作,询问第 33 个桶目前有多少毫升水,对应第一次输出 66
  • 第三次操作,24243333 一共有 22 个素数,因此第 11 个桶到第 55 个桶当前各有 22 毫升水;
  • 第四次操作,询问第 11 个桶到第 55 个桶现在一共有多少毫升水,注意到第 33 个桶的水在第三次操作的时候也变成了 22 毫升,因此 55 个桶一共有 1010 毫升水,对应第二次输出。

黄冈师范学院第1届ACM程序设计竞赛

未参加
状态
已结束
规则
ACM/ICPC
题目
10
开始于
2022-10-30 14:00
结束于
2022-10-30 18:00
持续时间
4 小时
主持人
参赛人数
0