#P15683. [Bulgarian2022训练营]robbery抢劫

[Bulgarian2022训练营]robbery抢劫

题目描述

Olympia 国的银行系统非常发达,因为居民们很喜欢储蓄。该国的货币单位是 tugrik。

全国有 NN 家银行,编号为 11 到 NN。编号为 ii 的银行中存有 aia_i 个 tugrik。

一开始,没有任何银行安装防抢劫的安保系统。不过该国有一条“明智”的规定:如果在第 dd 天晚上,编号为 bb 的银行被抢劫,那么在第 d+1d+1 天早上,编号为 b−1b-1 和 b+1b+1 的银行会安装安保系统,如果这些银行存在的话。安装安保系统的过程还会继续:对任意 i>0i>0,在第 d+id+i 天早上,编号为 b−ib-i 和 b+ib+i 的银行会安装安保系统,如果这些银行存在的话。

已经被抢劫过的银行不会再次被抢劫。

现在 Olympia 形成了一个由会解决复杂信息学问题的盗贼组成的团伙。他们计划连续实施一系列抢劫,使得在所有银行都被安保系统保护或已经被抢劫之前,抢到的钱数尽可能多。团伙每天晚上最多实施一次抢劫。

银行系统管理层想分析可能损失。他们要考虑 M+1M+1 种银行存款分布方案,编号为 11 到 M+1M+1。第 11 种是初始方案。每个后续方案都只是在前一个方案的基础上,改变恰好一家银行中的钱数。

对每一种方案,损失定义为盗贼在最优行动下能够抢到的最大钱数。

请你编写程序,求出每种方案对应的最大可能损失。

输入格式

第一行包含两个正整数 N,MN,M,分别表示银行数量和修改次数。

第二行包含 NN 个非负整数 aia_i,表示初始时第 ii 家银行的钱数。

接下来 MM 行,每行包含两个整数 B,TB,T,表示把编号为 BB 的银行中存放的钱数改为 TT。

输出格式

输出 M+1M+1 行。第 ii 行输出一个整数,表示第 ii 种银行存款分布方案下,盗贼最优行动能够抢到的最大钱数。

数据范围

  • 1≤N≤1051 \le N \le 10^5;
  • 1≤M≤1051 \le M \le 10^5;
  • 0≤ai≤1050 \le a_i \le 10^5。

部分测试限制:

  • 10%10\% 的测试中,1≤N≤81\le N\le 8,1≤M≤81\le M\le 8;
  • 50%50\% 的测试中,1≤N≤10001\le N\le 1000,1≤M≤10001\le M\le 1000。

每个测试点单独计分。

样例

输入

7 4
6 7 5 6 2 2 4
6 5
7 2
7 6
4 6

输出

17
18
18
19
19

样例解释

下面的状态中,0 表示银行已经被抢劫,-1 表示银行已经安装安保系统。

6 7 5 6 2 2 4      初始分布
6 7 5 0 2 2 4      抢劫了 4 号银行,得到 6 tugrik
6 7 -1 0 -1 2 4    次日早晨,3 号和 5 号银行安装安保系统
6 0 -1 0 -1 2 4    抢劫了 2 号银行,得到 7 tugrik
-1 0 -1 0 -1 -1 4  1 号和 6 号银行安装安保系统
-1 0 -1 0 -1 -1 0  抢劫了 7 号银行,得到 4 tugrik

此时不再存在既未被抢劫又未被保护的银行,所以团伙一共抢到 1717 个 tugrik。

最后一种方案为

6 7 5 6 2 5 6

此时最大收益为 6+7+66+7+6,可以通过抢劫第 44、第 22、第 77 家银行获得。