P16330 Just Because!

> 瑛太把刚才拍的樱花树的照片发了上去。写到“大学很普通”。 > > ——看起来就是这样的感觉啊。这是来自她的回答，很疑惑，“看什么”，这到底是怎么回事。 > > 然后 line 画面上发来一张照片。像是在哪里见过的景色，在散落了一半的樱花树下有一个驼背男大学生的后背。瑛太的背包，瑛太的衣服，照片里的是瑛太本人。 > >怀着惊讶和确信的心情，慢慢地回头看。她在后面，十步左右的距离，恶作剧似地笑着。 > > “我并不是为了追求泉来这的，是因为这里的教育系比较有名。” > 她开心地告诉了我不知道的事情，有很多想说的话。 > >我有很多想说的话，想听的事情也很多。但在她面前，瑛太想要传达的就只剩下，那天没有说出口的话，那天最想传达的想法... > > “夏目，我喜欢你。” > > 在林荫大道上刮起大风，稍强的风把樱花吹得飘落下来，落在两人身上。 > > “我也是，泉。” > > 在樱吹雪的风中，她害羞地笑了起来。

你有 $n$ 棵树，第 $i$ 棵树位于位置 $p_i$，高度为 $h_i$，保证 $p$ 单调递增。 给定 $q$ 次询问。对于第 $i$ 次询问，只保留 $[l_i,r_i]$ 子区间，你要选择最多的树，使得存在一种砍倒方式使得每棵树都不碰到另一棵树的树桩。 形式化地，设 $S = \{s_1, s_2, \dots, s_k\} \subseteq \{l_i, l_i+1, \dots, r_i\}$ 且 $s_1 < s_2 < \cdots < s_k$。 要求对任意 $1 < j < k$，都有 $p_{s_j} + h_{s_j} < p_{s_{j+1}} \lor p_{s_j} - h_{s_j} > p_{s_{j-1}} $。求 $\max k$。 询问之间互相独立。

第一行两个正整数 $n,q$。 第二行一个长度为 $n$ 的严格递增正整数序列 $p_i$。 第三行 $n$ 个正整数表示 $h_i$。 接下来 $q$ 行，每行两个正整数 $l_i,r_i$ 表示询问的区间。

共 $q$ 行，每行一个整数表示每个询问的答案。

**【数据范围】** **本题使用子任务捆绑**。 对于所有测试数据，$1\le n,q \le 5\times 10^5$，$1\le p_i,h_i \le 10^9$，$l_i\le r_i$。对于所有 $1\le i< n$，保证 $p_i < p_{i+1}$。 |子任务编号|$n\le$|$q \le$|特殊性质|分值| |:-:|:-:|:-:|:-:|:-:| |$1$|$18$|$18$|无|$10$| |$2$|$300$|$300$|无|$20$| |$3$|$3000$|$3000$|无|$20$| |$4$|$10^5$|$10^5$|有|$10$| |$5$|$5\times 10^5$|$5 \times 10^5$|无|$40$| 特殊性质：对于所有 $1\le i\le q$，保证 $l_i=1$。