P12557 ！？球球？！

· · 题解

为叙述方便，后文下标使用 0-base。如果一个点在传球若干次之后能到达，则称其是可达的。

设 pos_i=\sum_{j=0}^{i-1} \mod n（pos_0=0），即 pos_i 为传球了 i 次后球的位置。设当前走到的最后一个点为 fin，容易得出：如果位置 p 可达，则位置 (p+k\times \gcd(fin,n))\mod n (k\in [1,+\infin)) 也可达。

注意到不超过 3\times 10^5 的正整数因数个数不会超过 180。这启示我们就因数进行预处理。

对于一个因数 num，我们可以分别求出模 num 等于 0,1,\dots,num-1 位置上的数的最小值，记为 mn_{num,i}。由于对一个因数进行预处理的时间复杂度为 \Omicron(n)，预处理不会超时。

接下来开始处理查询。可以维护 lst_i，表示上一次出现 \gcd(fin,n)=i 的询问是第几次；以及 ans_i，表示 \gcd(fin,n)=i 时的答案。若当前为第 i 次询问，\gcd(fin,n)=x，则将 ans_x 与 \min_{j\in [lst_x+1,i]}mn_{x,pos_j\mod x} 取最小值，也就是让尚未贡献的 pos_j 添加贡献。此时答案即为 ans_x。因为对于每个 x，添加贡献的次数都为 n，所以查询复杂度也为 \Omicron(n)。

时间复杂度 \Omicron(n)，带一个 180 的常数，可以通过。

附上 AC Code。

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=3e5+10;
int n,q,a[N],num[N],tot,pos[N],lst[N],ans[N];
vector<int> vec[N];
signed main(){
    cin>>n>>q;
    memset(ans,0x3f,sizeof ans);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=1;i*i<=n;i++){
        if(n%i==0){
            num[++tot]=i;
            if(i*i!=n)num[++tot]=n/i;
        }
    }
    sort(num+1,num+tot+1);
    for(int i=1;i<=tot;i++){//预处理最小值 
        lst[num[i]]=-1;
        for(int j=0;j<num[i];j++){
            int curmn=1e9;
            for(int k=j;k<n;k+=num[i])curmn=min(curmn,a[k]);
            vec[num[i]].push_back(curmn);
        }
    }
    for(int i=1,x;i<=q;i++){
        cin>>x;pos[i]=(pos[i-1]+x)%n;
        int gc=__gcd(pos[i],n);
        for(int j=lst[gc]+1;j<=i;j++){//添加贡献 
            ans[gc]=min(ans[gc],vec[gc][pos[j]%gc]);
        }
        lst[gc]=i;
        cout<<ans[gc]<<" ";
    }
    return 0;
}