gmoj 6818. 【2020.10.07提高组模拟】数列递推

 来自LOJ上的原题。

考场想到了结论，但是以为会超时，所以没打。

很明显，当ai*ai-1>0时，后面的a都是递增或递减的，所以可以利用这个条件做这道题。

暴力计算ai，直到ai*ai-1>0，可以证明这个的时间是log(k+1,1e7)的：

　　设bi表示abs(a[i])，a[i]>0,a[i-1]<0，易得b[i-1]>b[i],则有b[i]=b[i-2]-k*b[i-1]<b[i-2]-k*b[i],所以就有b[i]*(k+1)<b[i-2]，这样就证完了。

注意一下实现细节。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500000
#define ll long long
using namespace std;
ll n,m,s[N],i,a[N],k,mxs,mns,p,st;
int main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
    scanf("%lld",&m);
    for (i=1;i<=m;i++)
        scanf("%lld",&s[i]);
    scanf("%lld",&n);
    while (n--){
        scanf("%lld%lld%lld",&a[0],&a[1],&k);
        mxs=-1,mns=-1;
        st=0;
        if (s[1]==0){
            if (mxs==-1||a[0]>a[mxs]) mxs=0;
            if (mns==-1||a[0]<a[mns]) mns=0;
            st++;
        }
        if (s[1]==1){
            if (mxs==-1||a[1]>a[mxs]) mxs=1;
            if (mns==-1||a[1]<a[mns]) mns=1;
            st++;
        }
        if (m>=2&&s[2]==1){
            if (mxs==-1||a[1]>a[mxs]) mxs=1;
            if (mns==-1||a[1]<a[mns]) mns=1;
            st++;
        }
        p=1;
        while (a[p]*a[p-1]<=0){
            p++;
            a[p]=a[p-1]*k+a[p-2];
            if (m>=st+1&&s[st+1]==p){
                st++;
                if (mxs==-1||a[p]>a[mxs]) mxs=p;
                if (mns==-1||a[p]<a[mns]) mns=p;
            }
            if (m==st) break;
            if (a[p]==0&&a[p-1]==0)
                break;
        }
        if (a[p]==0&&a[p-1]==0){
            if (st==0)
                mns=mxs=s[1];
        }
        if (a[p]*a[p-1]>0)
        if (a[p]>0){
            while (mxs>=0&&a[p]<a[mxs]){
                p++;
                a[p]=a[p-1]*k+a[p-2];
                if (m>=st+1&&s[st+1]==p){
                    st++;
                    if (mxs==-1||a[p]>a[mxs]) mxs=p;
                    if (mns==-1||a[p]<a[mns]) mns=p;
                }
                if (s[st+1]==p) st++;
                if (m==st) break;
            }
            if (st<m) mxs=s[m];
            if (st==0) mns=s[1];
        }
        else{
            while (mns>=0&&a[p]>a[mns]){
                p++;
                a[p]=a[p-1]*k+a[p-2];
                if (m>=st+1&&s[st+1]==p){
                    st++;
                    if (mxs==-1||a[p]>a[mxs]) mxs=p;
                    if (mns==-1||a[p]<a[mns]) mns=p;
                }
                if (s[st+1]==p) st++;
                if (m==st) break;
            }
            if (st<m) mns=s[m];
            if (st==0) mxs=s[1];
        }
        printf("%lld %lld
",mxs,mns);
    }
    return 0;
}