description
sosusosu 虐爆 OI 之后成为了一名文化课选手。一天，他做作业碰到了一堆数列问题，每道题给出的数列都是以下形式：
给定一个下标从
0
0
0开始，无限长的整数列
a
i
{a_{i}}
ai，
i
∈
N
i \in N
i∈N ，已知
a
0
,
a
1
a_{0},a_{1}
a0,a1 的值，以及递推式
a
i
+
2
=
k
a
i
+
1
+
a
i
a_{i+2}=ka_{i+1}+a_{i}
ai+2=kai+1+ai，
i
∈
N
i \in N
i∈N ，
k
∈
N
+
k \in N^+
k∈N+。
sosusosu 研究了这些数列，发现它们十分优美充满人类智慧，于是决定出一道 OI 题。sosusosu 给了你一个集合
S
⊂
N
S\subset N
S⊂N，他想问你对于
S
S
S中的每个数
s
i
s_i
si，使得
a
s
i
a_{s_{i}}
asi最大的
s
i
s_{i}
si使得
a
s
i
a_{s_{i}}
asi最小的
s
i
s_{i}
si分别是多少。如果这样的
s
i
s_{i}
si有多个，请你回答最小的一个。另外，sosusosu 准备对他作业中碰到的每个数列都让你回答一次，不过每次的集合
S
S
S是一样的。数列数量
n
≤
3
∗
1
0
5
n\le3*10^5
n≤3∗105,
S
S
S中的元素个数
m
≤
1
0
5
m\le 10^5
m≤105
solution
手玩几组样例，可以得到一个结论：序列在经过某一个临界点之后会变成单调递增或单调递减，且最多只有前
l
o
g
2
k
log_2{k}
log2k个数是不单调的，请读者自证我太菜了不会证明故暴力判断前
l
o
g
2
k
log_2{k}
log2k个数，然后根据序列的单调性判断
S
S
S中最大的一个数是最大值还是最小值即可注意如果前
l
o
g
2
k
log_2{k}
log2k个数中没有任何一个在
S
S
S中，那么答案就会是
S
1
S_1
S1，需要特判
code
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
inline int read(){
int x
=0,f
=1;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-') f
=-1;ch
=getchar();}
while(isdigit(ch
)){x
=(x
<<3)+(x
<<1)+(ch
^48);ch
=getchar();}
return x
*f
;
}
const int N
=3e5+10;
const int M
=1e5+10;
int m
,n
,s
[M
],w
[M
];
ll a
[N
];
int main(){
m
=read();
for(int i
=1;i
<=m
;++i
){
s
[i
]=read();
}
n
=read();
while(n
--){
a
[0]=read();a
[1]=read();
int k
=read();
int fi
=min(100,s
[m
]);
ll mx
=-1e16,mn
=1e16;
int mxp
=-1,mnp
=-1;
for(int i
=2;i
<=fi
;++i
){
a
[i
]=1ll*k
*a
[i
-1]+a
[i
-2];
if(a
[i
]>1e15&&a
[i
-1]>=0&&a
[i
-2]>=0&&a
[i
]>=0){fi
=i
;break;}
if(a
[i
]<-1e15&&a
[i
-1]<=0&&a
[i
-2]<=0&&a
[i
]<=0){fi
=i
;break;}
}
for(int i
=1;i
<=m
;++i
){
if(s
[i
]<fi
){
if(a
[s
[i
]]>mx
) mx
=a
[s
[i
]],mxp
=s
[i
];
if(a
[s
[i
]]<mn
) mn
=a
[s
[i
]],mnp
=s
[i
];
}
else break;
}
if(a
[fi
]>mx
&&a
[fi
]>0)mxp
=s
[m
];
if(a
[fi
]<mn
&&a
[fi
]<0)mnp
=s
[m
];
if(mxp
==-1)mxp
=s
[1];
if(mnp
==-1)mnp
=s
[1];
printf("%d %d\n",mxp
,mnp
);
}
return 0;
