P3509 [POI 2010] ZAB-Frog——双指针+快速幂（倍增）

· · 个人记录

初见思路倍增

关于一次跳跃所到达的石子

初见二分

可以发现当处理到 i 的时候，左右两边是单调的（左边单调递减，右边单调递增）

而对于我们要跳的距离 s 来说，其的排名也是单调的

于是可以想到二分套二分，时间复杂度 O(n \log n \log \sum_{i=1}^{n} s_i)

敲得半死交上去发现只有60pts，拿计算器一算发现复杂度过高过不了

双指针

（怎么每次二分过不了双指针都能优化）

可以发现，对于距离某个点i前k小的点所在的区间都是连续的，可以结合之前的单调性用反证法证明

那么，考虑区间移动的情况，当到 r+1 的距离 < 到 l 的距离时，区间右移

（也很好证明，因为当到 r+1 的距离更小时， l 就被踢出前 k 小了）

时间复杂度 O(n)

关于 m 次跳跃

朴素倍增

开一个 n \log m 的倍增表，然后该怎么倍增怎么倍增

时间复杂度 O(n \log m)

但是空间不够（又是打完之后MLE才知道的）

滚动数组？快速幂？

可以发现对于所有的位置，都有相同的次数 m ，那么我们在每次跳的时候全部一起跳，然后把之后用不到的给扔了

可以叫它滚动数组也可以叫它快速幂或者别的什么，反正把空间压到 n 了

（好像矩阵乘法欸）

AC Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll MAXN=1e6+5;

int nxt[MAXN],tmp[MAXN],ans[MAXN];
ll n,m,k;

ll a[MAXN],tot=0;

void getfir(){
    int l=1,r=k+1; 
    for(ll i=1;i<=n;++i){
        while(r+1<=n && abs(a[r+1]-a[i])<abs(a[l]-a[i])) ++l,++r;
        if(abs(a[l]-a[i])>=abs(a[r]-a[i])) nxt[i]=l;
        else nxt[i]=r;
    }//双指针 
}//

void change(){
    for(int i=1;i<=n;++i)
        tmp[i]=nxt[i];
    for(int i=1;i<=n;++i)
        nxt[i]=tmp[tmp[i]];
}//一次平方 

void getst(){
    for(int i=1;i<=n;++i)
        ans[i]=i;

    while(m){
        if(m&1){
            for(int i=1;i<=n;++i)
                ans[i]=nxt[ans[i]];
        }
        m>>=1;
        change();
    }
}//快速幂 

void work(){
    scanf("%lld%lld%lld" ,&n,&k,&m);

    for(ll i=1;i<=n;++i)
        scanf("%lld",&a[i]);

    getfir();
    getst();

    for(ll i=1;i<=n;++i)
        printf("%lld ",ans[i]);
} 

int main(){
    work();
    return 0; 
}

//这篇看过题解了