题目
有个非负整数集合
S
S
S，大小为
m
m
m。
接下来会有
n
n
n个询问，每次询问对于一个数列，给出
a
0
,
a
1
,
k
a_0,a_1,k
a0,a1,k，递推式为
a
i
+
2
=
k
a
i
+
1
+
a
i
a_{i+2}=ka_{i+1}+a_i
ai+2=kai+1+ai，
max
x
∈
S
a
x
\max_{x\in S} a_x
maxx∈Sax为多少。
n
≤
3
∗
1
0
5
n\le 3*10^5
n≤3∗105
m
≤
1
0
5
m\le 10^5
m≤105
比赛的时候直接推通项来搞，最终被它的精度问题搞死了。。。
假如存在相邻的两项不异号，那么后面将会是单调的。
尝试去找到第一个相邻两项不异号的，然后可以发现它的下标是
O
(
log
k
+
1
)
O(\log_{k+1})
O(logk+1)级别的。
具体证明考虑相邻异号的序列最长有多长，可以发现为了维持它相邻异号，数列隔一个的值会缩小到至多
1
k
+
1
\frac{1}{k+1}
k+11左右。
于是暴力找出这个位置，并且往后一直算到绝对值大于等于前两项的位置。
后面怎么做就显然了。
using namespace std
;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#define M 100005
#define ll long long
int m
,s
[M
];
ll k
;
ll a
[M
];
ll mx
,mn
,ansx
,ansn
;
void upd(ll v
,ll id
){
if (ansx
==-1 || v
>mx
|| v
==mx
&& id
<ansx
) ansx
=id
,mx
=v
;
if (ansn
==-1 || v
<mn
|| v
==mn
&& id
<ansn
) ansn
=id
,mn
=v
;
}
int main(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
scanf("%d",&m
);
for (int i
=1;i
<=m
;++i
)
scanf("%d",&s
[i
]);
int Q
;
scanf("%d",&Q
);
while (Q
--){
scanf("%lld%lld%lld",&a
[0],&a
[1],&k
);
int n
=0;
for (;a
[n
]*a
[n
+1]<0;++n
)
a
[n
+2]=a
[n
+1]*k
+a
[n
];
if (a
[n
]+a
[n
+1]>0){
for (;a
[n
]<max(a
[0],a
[1]);++n
)
a
[n
+2]=a
[n
+1]*k
+a
[n
];
}
else{
for (;a
[n
]>min(a
[0],a
[1]);++n
)
a
[n
+2]=a
[n
+1]*k
+a
[n
];
}
ansx
=ansn
=-1;
int i
=1;
for (;i
<=m
&& s
[i
]<=n
+1;++i
)
upd(a
[s
[i
]],s
[i
]);
if (s
[m
]>n
+1){
if (a
[n
]+a
[n
+1]>0){
if (ansn
==-1) ansn
=s
[1];
upd(LLONG_MAX
,s
[m
]);
}
else if (a
[n
]+a
[n
+1]<0){
if (ansx
==-1) ansx
=s
[1];
upd(LLONG_MIN
,s
[m
]);
}
else
upd(0,s
[i
]);
}
printf("%lld %lld\n",ansx
,ansn
);
}
return 0;
}
