P8348 「Wdoi-6」未知之花魅知之旅

[](https://thwiki.cc/%E6%9C%AA%E7%9F%A5%E4%B9%8B%E8%8A%B1_%E9%AD%85%E7%9F%A5%E4%B9%8B%E6%97%85) 位于太平洋板块和亚欧板块消亡边界的日本，是世界上最多发地震的一个国家之一。2011 年 3 月 11 日，日本时间下午 2 时 46 分 18 秒，一场里氏 9 级的地震袭击了这个国家，随之而来的，是超过 10 米高的巨大海啸。妻离子散，家破人亡，是对这一悲剧性事件的最好描述。 2011 年 5 月，东方 Project 的创作者 ZUN，为地震中的灾民谱写了一张专辑，叫做《未知之花，魅知之旅》，所筹得的善款都被捐赠用于救灾赈灾之中。 ----- 而到了近未来的科学世纪，莲子和梅莉在一次聊天之中，又谈论到了这场大地震。这场地震对传统宗教的摧残程度也颇深，数千所神社不同程度遭受到了损毁，也有不少神社的主殿全毁或者半毁。甚至就连外界的博丽神社，也因此被摧毁。 莲子与梅莉决定动身，前往外界的博丽神社，进入幻想乡中，通报这一消息。

### 简要题意 称一个长度为 $n$ 的正整数数列是「$k$ - 好」的，当且仅当它满足以下条件： - 对于 $1< i< n$，满足 $a_{i-1},a_i,a_{i+1}$ 中最大的一个等于其他两个之和。 - 所有元素都不小于 $k$。 $T$ 组询问，每次询问给定 $(a_0,a_1,x,y,k)$，问是否存在「$k$ - 好」数列（长度不小于 $2$），前两项为 $a_0,a_1$ 并且有相邻两项依次为 $x,y$。 ----- ### 原始题意 原本就门可罗雀的博丽神社，在地震之后，更显荒凉。莲子与梅莉紧赶慢赶来到了博丽神社，只看到了倒塌的鸟居。由于神社过于荒凉，莲子和梅莉决定先将神社给好好打扫一番，再进入幻想乡。 具体而言，神社中有若干个物件等待被整理，每个物件都有一个正整数魅力值。可以认为，每种魅力值的物件都有**足够多**个。从被遗落的绘马中，莲子得知了，在被地震摧毁前的博丽神社中的物件，应当具有如下特点： - 每个物件都有一个**不小于** $k$ 的魅力值。 - 三个相邻物件的**最大**魅力值，是其他两个物件的魅力值**之和**。 - 前两个物件的魅力值分别为 $a_0, a_1$。 - 存在**相邻**的两个物件，魅力值依次为 $x, y$。 莲子和梅莉认为，如果能够从所有物件中选出一些进行排列，并满足如上特点的话，那么这样的神社是**美观**的，不会让她们一进入幻想乡就被灵梦退治。 很显然，由于物件的散佚，莲子和梅莉可能无法通过这些信息来使得神社变得**美观**。莲子和梅莉找到了你，希望你能告诉她们，在这样的规则下是否存在一种让神社变得**美观**的方案。 由于灵梦退治得太狠，她们担心自己的生命安全，因此她们会对你询问 $T$ 次，以确保你不是在糊弄她们。

无

无

### 样例解释 - 针对第一次询问，$a_0=2,a_1=3$，莲子和梅莉可以将物件如下排列构造：$2,3,5,2,7,9,2,11,\dots$，其中 $a_5=7,a_6=9$，从而存在方案让神社变得美观。 - 针对第二次询问，$a_0=4,a_1=9$，莲子和梅莉可以将物件如下排列构造：$4,9,5,4,1,3,2,5,3,8,\dots$，其中 $a_6=2,a_7=5$，从而存在方案让神社变得美观。 - 针对第三次询问，由于要求 $a_i \geq k=2$，第二次询问中的方法失效，同时也可以证明不存在让神社变得美观的方法。 - 针对第四次询问，要求构造出的 $x=1,y=2$ 都小于等于 $3$，从而无法让神社变得美观。 - 针对第五次询问，显然 $a_0=7,a_1=9$ 就已经符合让神社变得美观的要求了。 ### 数据范围 **本题采用捆绑测试。** 令 $n=\max(a_0,a_1,x,y,k)$。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{T\le } & \bm{n\le } & \textbf{\textsf{特殊性质}} & \textbf{Subtask \textsf{依赖}}\cr\hline 1 & 10 & 10 & 10 & - & - \cr\hline 2 & 20 & 300 & 1000 & \mathbf{A} & - \cr\hline 3 & 10 & 300 & 10^9 & \mathbf{B} & - \cr\hline 4 & 20 & 300 & 10^8 & \mathbf{C} & 1,2 \cr\hline 5 & 40 & 10^5 & 10^9 & - & 3,4 \cr\hline \end{array} $$ - 特殊性质 $\mathbf{A}$：每次询问的 $k$ 相同。 - 特殊性质 $\mathbf{B}$：$k=1$。 - 特殊性质 $\mathbf{C}$：$\sum n \leq 10^8$。 对于 $100\%$ 的数据，$1 \leq n \leq 10^9,1 \leq T \leq 10^5$。