#576. 「LibreOJ NOI Round #2」签到游戏

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

传说在上古时代,有一个简单的签到游戏。能通关这个游戏的幸运挑战者,将会收到一份小礼包。

签到游戏是这样的:

出题人有 n 个不透明的杯子,倒扣在桌面上,排成一列。这些杯子从左到右依次编号为 1 n ,第 i 个杯子里放着 A_i 个小球。当然,由于杯子是不透明且倒扣着的,挑战者并不知道 A_i 的具体数值

出题人对于第 i 个杯子还设置了一个权值 B_i B_i 对挑战者公开

挑战者可以进行无限多轮操作。在一轮操作中,挑战者可以指定介于 1 n 之间的 l,r ,花费 \gcd_{i=l}^r B_i 的代价,获取第 l 个至第 r 个杯子里的小球总数,也即获取 \sum_{i=l}^r A_i 的具体数值。其中, \gcd_{i=l}^r B_i 表示 \gcd(B_l,B_{l+1},\dots,B_r)

挑战者需要达成的目标是:用尽量小的代价,正确地回答出题人,每个杯子里放着多少个小球,也即回答对于 1\leq i\leq n A_i 的具体数值。

现在,有 q 个挑战者依次进行挑战。他们将告知你他们得到的 B_i ,并希望你帮忙求出每个人为保证达成目标所需的最小代价。

经过你的观察,在第 k 个挑战者挑战前,出题人会在上个挑战者的 \{A_i\},\{B_i\} 基础上,不改变 n ,重新随机生成 \{A_i\} ,并修改 B 序列的某个特定位置 p_k B_{p_k} ,其余不变。

对于第一个挑战者,出题人会在初始序列的基础上修改。

如果你帮所有挑战者算出了正确的答案,他们会送给你一份礼物 —— 100 分。

输入格式

从标准输入读入数据。

第一行为两个整数 n,q ,分别表示出题人的杯子个数与挑战者个数。

第二行为 n 个正整数,第 i 个正整数表示初始时的 B_i

接下来 q 行中,第 k 行两个正整数 p_k,B_{p_k} ,表示第 k 个人挑战前出题人修改 B 序列的位置,与修改后的数值。

输出格式

输出到标准输出。

输出 q 行,第 k 行为一个整数,表示第 k 个挑战者达成目标所需要的最小代价。

样例

样例输入

5 5
1 2 3 4 5
1 2
3 4
5 6
1 8
2 4

样例输出

5
6
10
10
12

样例解释

第一个挑战者得到的 B=\{2,2,3,4,5\} ,可以证明,其最优选择之一为 [1,5],[1,3],[2,5],[1,4],[3,5] ,最小代价为 5 。其中 [x,y] 表示一次 l=x,r=y 的操作。

第二个挑战者得到的 B=\{2,2,4,4,5\} ,可以证明,其最优选择之一为 [1,4],[3,5],[1,5],[4,5],[2,5] ,最小代价为 6

对于其他的挑战者不再赘述。

数据范围与提示

对于所有数据,保证有 1\leq n\leq 10^5 1\leq q\leq 10^5 1\leq B_i\leq 10^9 1\leq p_i\leq n

子任务编号 分值 n\leq q\leq 特殊性质
1 12 200 200
2 20 10^5 1
3 23 1000
4 10 10^5 B_i [1,10^9] 的整数中等概率随机分布
5 35