scx 虐爆 OI 之后成为了一名文化课选手。一天，她做作业碰到了一堆数列问题，每道题给出的数列都是以下形式：

scx 研究了这些数列，发现它们十分优美，充满人类智慧，于是决定出一道 OI 题。

scx 给了你一个集合 $S \subset \mathbb{N}$，她想问你对于 $S$ 中的每个数 $s_i$，使得 $a_{s_i}$ 最大的 $s_i$ 和使得 $a_{s_i}$ 最小的 $s_i$ 分别是多少。如果这样的 $s_i$ 有多个，请你回答最小的一个。

另外，scx 准备对她作业中碰到的每个数列都让你回答一次，不过每次的集合 $S$ 是一样的。

输入格式

第一行包含一个正整数 $m$ ($m \leq 10^5$)，表示 $S$ 中元素个数。

第二行包含 $m$ 个非负整数 $s_1, s_2, \cdots, s_m$ ($s_i \leq 10^9$)，表示 $S$ 中的元素。保证它们严格递增 (即 $s_i < s_{i+1}$)。

第三行包含一个正整数 $n$ ($n \leq 3 \times 10^5$)，表示询问的数列个数。

接下来的 $n$ 行，每行包含三个整数 $a_0, a_1, k$ ($|a_0|, |a_1| \leq 10^7, 1 \leq k \leq 5 \times 10^3$)，描述一个数列。

输出格式

输出共 $n$ 行，每行依次输出两个整数 $\max s_i, \min s_i$，依次表示 $S$ 的元素 $s_i$ 中，使得 $a_{s_i}$ 最大的 $s_i$ 和使得 $a_{s_i}$ 最小的 $s_i$ 的值。如果这样的 $s_i$ 有多个，请你回答最小的一个。

题解

注意到 $k$ 为正整数这个条件和几个样例，我们大概可以感觉到，由这个递推式定义的数列，在若干项以后是单调的，且要么递增趋向正无穷大，要么递减趋向负无穷大。

如果 $a_0 a_1 > 0$，则 $a_0, a_1$ 同号，由递推式 $a_{i+2} = k a_{i+1} + a_i$ 知 $a_2$ 与 $a_1, a_0$ 均同号，且 $|a_2| > |a_1|$，继续由递推式和数学归纳法，可知结论成立。

如果 $a_0 a_1 < 0$，我们仅考虑 $a_0 > 0, a_1 < 0$ 的情况 (否则令 $a'_i = -a_i$ 即可)，那么记 $b_i = (-1)^i a_i$，则有 $b_{i+2} = b_i - k b_{i+1}$，如果 $b_i$ 一旦有负项，设 $b_j$ 为 $\left\{ b_i \right\}$ 的第一个负项，又 $b_{j-1}$ 为正项，故 $a_{j-1}$ 和 $a_j$ 同号，转为第 1 种情况。

如果存在相邻的两正项满足 $b_i < b_{i+1}$，则 $b_{i+2} = b_i - k b_{i+1} \leq b_i - b_{i+1} < 0$ 为负项，转为第 1 种情况。

因此只需考虑 $b_i$ 中 单调递减的正项最多会持续几项的问题。

由于 $b_i = k b_{i+1} + b_{i+2} > k b{i+2} + b_{i+2} = (k+1) b_{i+2}$，因此有 $b_{i+2} < \dfrac 1 {k+1} b_i$，于是这样的项最多有 $M \sim 2 \log b_0 = 2 \log a_0$ 项，大概是 $40$ 项左右，就会出现 $\left\{ a_i \right\}$ 中相邻两项同号的情况，从而结论成立。

是的。当 $a_0 a_1 = 0$ 时，$a_0 = 0$ 或 $a_1 = 0$。若 $a_0 = 0, a_1 \neq 0$，则会趋向于 $a_1$ 的符号，如果 $a_0 \neq 0, a_1 = 0$，则 $a_2 = a_0$，会趋向于 $a_0$ 的符号。

但当 $a_0 = a_1 = 0$ 时，$\left\{ a_i \right\}$ 为常数列 $a_i = 0$，此时需要特判，答案显然为 $s_1 \; s_1$。

这样一来，整个问题就简单了，先用 double 等不会溢出的数据类型算 $M$ 项，得到它趋向正无穷大，还是趋向负无穷大，接下来考虑它趋向正无穷大 (负无穷大类似)。

对于 $s_i$，可以先暴力出 $s_i$ 比较小时的最大值点和最小值点即可，如果有比较大的 $s_i$，标记一下 $s_i$ 中的最大者 $T$，把最大值点更新为 $T$。

时间复杂度为 $O(n M)$，其中 $M$ 定义见上，为可能保持不单调的最多项数，然后写个 IO 优化 ~~(貌似不写也可以？)~~ 就可以过了。

代码

#include <bits/stdc++.h>
#define N 100034
using namespace std;

const int threshold = 40;

bool increasing;
int n, q, i;
int u, v, k;
double a[45];
int s[N], super = -1;
int maxSi, minSi;

int main(){
    scanf("%d", &n);
    for(i = 0; i < n; ++i) scanf("%d", s + i);
    for(i = 0; i < n; ++i) if(s[i] >= threshold) {super = s[n - 1]; n = i; break;}
    for(scanf("%d", &q); q; --q){
        scanf("%d%d%d", &u, &v, &k);
        if(!(u || v)) {printf("%d %d\n", *s, *s); continue;}
        a[0] = (double)u; a[1] = (double)v;
        for(i = 2; i <= threshold; ++i) a[i] = (double)k * a[i - 1] + a[i - 2];
        maxSi = minSi = s[0];
        for(i = 1; i < n; ++i){
            a[s[i]] > a[maxSi] ? maxSi = s[i] : 0;
            a[s[i]] < a[minSi] ? minSi = s[i] : 0;
        }
        if(~super) (a[threshold] > 0.0 ? maxSi : minSi) = super;
        printf("%d %d\n", maxSi, minSi);
    }
    return 0;
}

坑

坑1：再暴力前 $M$ 项的过程中不能用 int，可能会因为溢出而得到错误的结果。可以使用 long long, double 等不会溢出的数据类型。

坑2：千万不要忘记特判 $a_0 = a_1 = 0$！此时无论怎样答案都是 $s_1 \; s_1$，即 $S$ 中最小的数。

题目描述

输入格式

输出格式

题解

代码

坑