【Codeforces 1032G】Chattering | Mrsrz's blog

ST 表，倍增。

题目大意：

有 $n$ 个人围成一圈，要传递消息。第 $i$ 个人会在 $1$ 个时刻内把消息传递到距离他不超过 $a_i$ 的人。

问第 $0$ 时刻分别只有 $1,2,3,\ldots,n$ 知道消息时，各需要多少时间才能把消息传递到所有人。

题解：

考虑序列上怎么做。

容易发现，每一时刻传递到信息的人一定是连续的，记录这段区间为 $[l,r]$。

那么下一次传递，我们就让 $[l,r]$ 中能往左、右传递最远的两个点进行传递。

这个可以用 ST 表维护区间最值，然后 $O(1)$ 单次跳。

但是这样复杂度还是 $O(n^2)$。

容易想到倍增。我们开 $\log n$ 个 ST 表，分别维护一个点跳 $2^n$ 次能跳到的最左、右端点（中间可能切换方向更优所以要同时维护）。

然后查询的时候也倍增即可。

时空复杂度 $O(n\log^2n)$。

考虑在圈上怎么做。

将序列变成 $3$ 倍长度，建 ST 表。

然后从中间开始倍增。如果某次跳完之后，区间长度大于等于 $n$ 则说明完全覆盖。以此来倍增即可。

时空复杂度 $O(n\log^2 n)$。

但是 $3$ 倍空间开不下。

由于三份的查询是类似的，所以可以只开 $1$ 倍空间，然后每次查询就分三段进行即可。

这样能正好卡进 $256\texttt{MB}$。

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
#define lg2(x)(31^__builtin_clz(x))
using namespace std;
const int N=100005;
int n,a[N];
struct Right{
    int mx[N],st[17][N];
    inline int&operator[](const int&x){return mx[x];}
    void init(){
        memcpy(*st,mx,sizeof mx);
        for(int i=1;i<17;++i)
        for(int j=1;j+(1<<(i-1))<=n;++j)
        st[i][j]=max(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    }
    inline int query(int l,int r){
        if(l>r)return-(1<<30);
        const int g=lg2(r-l+1);
        return max(st[g][l],st[g][r-(1<<g)+1]);
    }
    inline int Q(int l,int r){
        return max({query(max(l,1),min(r,n)),n+query(max(l,n+1)-n,min(r,2*n)-n),-n+query(max(l,-n+1)+n,min(r,0)+n)});
    }
}R[17];
struct Left{
    int mn[N],st[17][N];
    inline int&operator[](const int&x){return mn[x];}
    void init(){
        memcpy(*st,mn,sizeof mn);
        for(int i=1;i<17;++i)
        for(int j=1;j+(1<<(i-1))<=n;++j)
        st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    }
    inline int query(int l,int r){
        if(l>r)return 1<<30;
        const int g=lg2(r-l+1);
        return min(st[g][l],st[g][r-(1<<g)+1]);
    }
    inline int Q(int l,int r){
        return min({query(max(l,1),min(r,n)),n+query(max(l,n+1)-n,min(r,2*n)-n),-n+query(max(l,-n+1)+n,min(r,0)+n)});
    }
}L[17];
void init(){
    for(int i=1;i<17;++i){
        L[i-1].init();
        R[i-1].init();
        for(int j=1;j<=n;++j)
        L[i][j]=L[i-1].Q(L[i-1][j],R[i-1][j]),
        R[i][j]=R[i-1].Q(L[i-1][j],R[i-1][j]);
    }
    L[16].init(),R[16].init();
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    if(n==1)return puts("0"),0;
    for(int i=1;i<=n;++i)
    cin>>a[i];
    for(int i=1;i<=n;++i)
    R[0][i]=i+a[i],L[0][i]=i-a[i];
    init();
    for(int i=1;i<=n;++i){
        int ans=0,l=i,r=i;
        for(int j=16;~j;--j){
            int nL=L[j].Q(l,r),nR=R[j].Q(l,r);
            if(nR-nL+1<n)ans|=1<<j,l=nL,r=nR;
        }
        printf("%d ",ans+1);
    }
    return 0;
}