雨

(rain.cpp 1s/512MB)

题目背景

LTF 卷的速度 Faster Than Light。

题目描述

机房里有 $`2^n`$ 个人，每个人有一个幸福指数 $`a_i`$ ，保证 $`a_i`$ 是自然数。

外面正下着大雨，没有人离开机房。LTF 打算掀起一场卷王狂潮！卷王狂潮总共会持续 $`n`$ 轮，每一轮开始时，所有未被淘汰的人会按原本的顺序重新编号，然后第 $`2i-1`$ 个和第 $`2i`$ 个人开始相互竞争，幸福指数更小的人会被淘汰（如果幸福指数相同编号大的人被淘汰），胜出的人的幸福指数会减去被淘汰的人的幸福指数，然后进入下一轮的角逐。

最终胜出的人会加冕为“卷怪”。LTF 是第一个人，他有金手指，每使用一次金手指就可以增加一点幸福指数。LTF 想成为卷怪，为此他已经偷偷地打开了完全隐私保护，但他又不想使用过多次金手指。你能告诉他他最少使用多少次金手指就能加冕为“卷怪”吗？

当然，每个人的幸福指数不是一成不变的。在接下来的 $`m`$ 天，机房众人的幸福指数会有所变化。具体地，第 $`i`$ 天开始时，编号处于 $`[l_i,r_i]`$ 中的人的幸福指数会增加 $`x_i`$ 。对于每个 $`i`$ ，你都需要告诉 LTF，如果他想在第 $`i`$ 天掀起卷王狂潮并加冕为“卷怪”，他当天最少需要使用多少次金手指。注意，LTF 只是在做计划，并没有真的掀起卷王狂潮让众人的幸福指数因为卷而改变。

输入格式

第一行包含两个整数 $`n,m`$ ，表示机房里总共有 $`2^n`$ 个人，

第二行共有 $`2^n`$ 个整数，表示每个人的幸福指数。其中第 $`i`$ 个整数 $`a_i`$ 表示第 $`i`$ 个人的幸福指数。LTF 是第一个人。

接下来 $`m`$ 行，第 $`i`$ 行包含三个整数，依次为 $`l_i,r_i,x_i`$ 。

输出格式

共 $`m`$ 行，每行包含一个整数，表示这天 LTF 最少使用多少次金手指。

输入输出样例 #1

输入 #1

输出 #1

2
11
10

输入输出样例 #2

输入 #2

4 2
2 4 7 9 5 9 1 3 8 6 2 2 9 8 2 6
1 1 0
3 4 1

输出 #2

7
7

说明/提示

由于输入量较大，请选手使用较快的读入方式。

如下代码能够较为快速地读入 $`n,m`$ 以及 $`a`$ 数组，您可以在此代码的基础上实现此题：

#include<bits/stdc++.h>
using namespace std;
int read();

signed main(){
    n=read();m=read();
    for(int i=1;i<=(1<<n);++i) a[i]=read(); //1<<n 等于2的n次方 
    //至此 n 和 a 数组均已读入完毕（a 数组下标从 1 开始） 
    
    return 0;
}

int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        ch=getchar();
        if(ch=='-') f=-1;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

对于第一组样例的第一天，LTF 可以使用 $`2`$ 次金手指使他的幸福指数变为 $`6`$ 。

第一轮开始时： $`(6,5),(3,2)`$ ，第二个人和第四个人被淘汰。

第二轮开始时： $`(1,1)`$ ，由于 LTF 的编号比另一个人小，所以 LTF 胜出。

数据范围

对于 $`10\%`$ 的数据， $`n=0`$ 。

对于 $`30\%`$ 的数据， $`a_i\le 42,n\le 8,m\le 10`$ 。

另有 $`40\%`$ 的数据， $`n\le 17,m=1`$ 。

对于 $`100\%`$ 的数据， $`0\le n\le 20,0\le a_i,x_i\le 10^{9},m\le 10^5`$ 。