P12151 【MX-X11-T5】「蓬莱人形 Round 1」俄罗斯方块

原题链接：。 --- 「興味がないこと本気じゃないもの全部後回しで」 「知ってることは知らんぷり 私は終わってる」 「恥ずかしい過去知ってるやつらの記憶消させて」 「迷惑かけてごめんってば ねえ誰か助けて」

给定一个长为 $n$ 的整数序列 $h_i$，再给定 $n$ 个二元组 $(a_i,b_i)$，和一个正整数 $k$。 对于每个位置 $p$，你可以进行如下操作之一： - 激活位置 $p$，选择一个位置 $j$ 满足 $1\le j-p\le k$，然后令 $h_p \leftarrow h_p + a_p$、$h_j \leftarrow h_j - b_p$。**每个位置最多激活一次**。 - 不激活位置 $p$。 有 $q$ 次询问 $(l_i,r_i,x_i)$，表示在只能激活位置 $p\in[l_i,r_i]$，且对应的 $j\in [p+1,\min(p+k,r_i)]$ 的条件下，可以选择多个位置激活，问此时是否存在一种激活方式使得 $\max_{t=l_i}^{r_i}h_t\le x_i$。 询问之间互相独立，即每次询问开始时序列 $h$ 被恢复到原始状态，每个位置均未选择操作方式。

无

无

**【样例解释 #1】** 对于询问 $(2,3,1)$，可以激活位置 $2$，令 $h_2 \leftarrow h_2 + a_2$、$h_3 \leftarrow h_3 - b_2$，最后的 $h$ 的区间 $[2,3]$ 为 $1,-6$，最大值为 $1$，符合要求。 对于询问 $(1,3,1)$，可以证明没有合法的操作方案。 **【数据范围】** **本题使用子任务捆绑**。 对于所有测试数据，$1 \le T \le 3$，$1 \le n \le 2 \times 10^4$，$1\le q \le 10^5$，$0\le h_i,a_i,b_i,x_i \le 10^6$，$1\le l_i \le r_i \le n$，$1\le k \le 5$。 |子任务编号|$n\le$|$q \le$|$k \le$|$T \le$|特殊性质|分值|时限| |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |$1$|$10$|$10$|$5$|$3$|无|$5$|1 s| |$2$|$1000$|$1000$|$5$|$1$|无|$10$|1 s| |$3$|$2\times 10^4$|$10^5$|$5$|$3$|A|$10$|4 s| |$4$|$10^4$|$10^4$|$3$|$1$|B|$5$|1 s| |$5$|$10^4$|$10^4$|$3$|$1$|无|$10$|1 s| |$6$|$2\times 10^4$|$2\times 10^4$|$4$|$1$|B|$5$|1 s| |$7$|$2\times 10^4$|$2\times 10^4$|$4$|$1$|无|$10$|1 s| |$8$|$2\times 10^4$|$4\times 10^4$|$4$|$2$|B|$5$|1 s| |$9$|$2\times 10^4$|$4\times 10^4$|$4$|$2$|无|$10$|1 s| |$10$|$2\times 10^4$|$10^5$|$5$|$3$|无|$30$|4 s| - 特殊性质 A：$\forall 1 \le i \le q,l_i=1,r_i = n$。 - 特殊性质 B：$\forall 1 \le i,j \le q,x_i = x_j$。 **【提示】** 请注意本题特别的时间限制。