关于此题时间复杂度

如题。

题解区全部都是“玄学”的暴力做法，但我分析是可以卡到 O(n^2) 的。

比如这么一份代码：

#include<bits/stdc++.h>
using namespace std;
const int mxn=1e5+5;
int n,k,t[mxn],l,v[mxn],b[mxn],m[mxn];
int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>t[i];
    for(int i=1;i<=k;++i)cin>>v[i];
    for(int i=1;i<=k;++i)cin>>b[i];
    for(int i=1;i<=k;++i){
        l=0;//注意！此处去掉了强制在线，和时间复杂度无关！把这行删掉就可以强制在线，是原题
        v[i]=(v[i]+l-1)%n+1;l=0;
        for(;m[v[i]]<b[i];){
            if(m[v[i]]==0)++l;
            m[v[i]]=b[i]--;
            v[i]=t[v[i]];
        }
        cout<<l<<' '<<cnt<<'\n';
    }
}

通过下面这份 generator 就可以卡到 O(n^2)：

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("b.in","w",stdout);
    int n=100000;
    cout<<n<<' '<<n<<'\n';
    for(int i=1;i<=n;++i)cout<<i%n+1<<' ';cout<<'\n';
    for(int i=1;i<=n;++i)cout<<i<<' ';cout<<'\n';
    for(int i=1;i<=n;++i)cout<<1<<' ';cout<<'\n';
}

但神奇的是我本机居然 0.2s 跑过了！

然后我开始合理怀疑是编译器优化掉了。

我们对源代码这么改一下：

#include<bits/stdc++.h>
using namespace std;
const int mxn=1e5+5;
int n,k,t[mxn],l,v[mxn],b[mxn],m[mxn];
int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>t[i];
    for(int i=1;i<=k;++i)cin>>v[i];
    for(int i=1;i<=k;++i)cin>>b[i];
    int cnt=0;
    for(int i=1;i<=k;++i){
        l=0;//注意！此处去掉了强制在线，和时间复杂度无关！
        v[i]=(v[i]+l-1)%n+1;l=0;
        for(;m[v[i]]<b[i];){
            if(m[v[i]]==0)++l;
            m[v[i]]=b[i]--;
            v[i]=t[v[i]];
            ++cnt;
        }
        cout<<l<<' '<<cnt<<'\n';
    }
}

实际上就是加了个计数器，统计总共跳了多少次for

而这次它就跑了2s+，通过输出的 cnt 也可以看出是真的跑了 O(n^2)。

所以这题正解真的是这么暴力跑吗？