#P13779. [2024年山东第二轮集训]粉兔的冰红茶(icetea)

    ID: 12981 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-树形 DP动态 DP模逆元快速幂

[2024年山东第二轮集训]粉兔的冰红茶(icetea)

题目描述

小粉兔喜欢喝冰红茶。

小粉兔的寝室里有N=2n−1N=2^n-1桶冰红茶,形如一棵完全二叉树。根节点编号是11;对于点2≤x≤N−12\le x\le N-1,xx的父亲节点是⌊x2⌋\lfloor\frac x2\rfloor。编号为ii的冰红茶中装着hih_i mL 冰红茶。

小粉兔掌管半个寝室的冰红茶。编号为N+12\frac{N+1}{2}到NN的冰红茶是小粉兔室友的;但是对于编号为11到N−12\frac{N-1}{2}的冰红茶,小粉兔可以任意修改hih_i。

小粉兔有一套自己的审美观点。他认为寝室里冰红茶的不和谐度为

$$\sum_{x=2}^{N} \left(h_x-h_{\lfloor\frac x2\rfloor}\right)^2$$

小粉兔可以修改h1h_1到h2n−1−1h_{2^{n-1}-1}。由于是冰红茶,hih_i可以被修改成任意的非负实数。小粉兔想知道最小的不和谐度是多少。

有时小粉兔的室友会修改一个hih_i值(N+12≤i≤N)(\frac{N+1}{2}\le i\le N),这时粉兔需要重新查询最小不和谐度。

由于答案可能是小数,你只需要输出最小不和谐度  mod 1000000007\bmod 1000000007 的值。

输入格式

第一行输入两个数n,qn,q。qq是修改的数量。

接下来N+12\frac{N+1}{2}个数,代表$h_{\frac{N+1}{2}}, h_{\frac{N+1}{2}+1}, \cdots, h_N$。

接下来qq行,每行两个数p,h′p, h',代表将hph_p修改为h′h'。保证N+12≤p≤N\frac{N+1}{2}\le p\le N。

输入中的hh均为整数。

输出格式

输出q+1q+1行,每行一个数,代表最小不和谐度  mod 1000000007\bmod 1000000007 的值。

第一行是修改之前的最小不和谐度;第i>1i>1行是第i−1i-1次修改之后的最小不和谐度。

样例1

Input
2 0
1 3
Output
2

样例2

Input
3 3
0 1 5 4
6 4
5 4
4 4
Output
333333342
583333342
333333345
0
Hint

最小值分别是193,5512,283,0\frac{19}{3},\frac{55}{12},\frac{28}{3},0。

数据范围

对于所有测试点,2≤n≤18,0≤q≤500000,0≤h≤1082\le n\le 18, 0\le q\le 500000, 0\le h\le 10^8。

测试点1-2. n=2n=2。

测试点3-5. q=0q=0。

测试点6-10. 无特殊限制。