#P4597. [Shoi2016]随机序列

    ID: 1771 传统题 2000ms 256MiB 尝试: 449 已通过: 256 难度: 6 上传者: 标签>难度分类提高组合数学贡献法构造与建模对称性分析数据结构普通线段树CF2100

[Shoi2016]随机序列

[SHOI2016] 随机序列

题目描述

给定一列数 a1,a2,…,ana_1,a_2,\ldots,a_n。在每对相邻的数之间各插入一个加号、减号或乘号,共可得到 3n−13^{n-1} 个表达式。按通常的运算优先级计算每个表达式的值,即先算乘法,再按从左到右的顺序加减。

每次操作把某个 ata_t 改为 vv,并询问此时所有表达式的值之和。修改永久生效,之后的操作以当前序列为基础。

输入格式

第一行两个正整数 n,Qn,Q,分别为序列长度和修改次数。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。接下来 QQ 行各有两个整数 ti,vit_i,v_i,表示将 atia_{t_i} 修改为 viv_i。

输出格式

输出 QQ 行。对于每个修改输出一行,包含一个整数,表示修改之后所有可能表达式的和,对 109+710^9+7 取模。

5 5
9384 887 2778 6916 7794
2 8336
5 493
3 1422
1 28
4 60
890543652
252923708
942282590
228728040
608998099

数据范围

所有数据满足 1≤n,Q≤1051\le n,Q\le10^5,1≤ti≤n1\le t_i\le n,0≤aj,vi≤1040\le a_j,v_i\le10^4。

  • 对于 20%20\% 的数据,n,Q≤20n,Q\le20。
  • 对于 50%50\% 的数据,n,Q≤1000n,Q\le1000。