Cut

D - Cut

对于一道题目，如果没有别的想法，那么就可以先从它的朴素解法入手，然后再想能不能找到优化它的方法。

对于这道题而言，朴素的解法就是用一个数组来维护每一个位置失配的最远位置，可以开一个数组\(fail[maxn]\)进行记录。但是在最极端的情况下，每次查询会被卡成\(O(n)\)的，所以，这个地方，我们用倍增法进行优化，这样每次查询的时间复杂度就降为了\(O(log(n))\)

// Created by CAD
#include <bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;
int a[maxn],lst[maxn],pos[maxn],fail[maxn][20];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        int x=a[i];
        for(int j=2;j*j<=x;++j){
            if(x%j==0){
                lst[i]=max(lst[i],pos[j]);
                pos[j]=i;
                while(x%j==0)
                    x/=j;
            }
        }
        if(x!=1){
            lst[i]=max(lst[i],pos[x]);
            pos[x]=i;
        }
        fail[i][0]=max(lst[i],fail[i-1][0]);
        for(int k=1;k<=19;++k)
            fail[i][k]=fail[fail[i][k-1]][k-1];
    }
    while(q--){
        int l,r;cin>>l>>r;
        int ans=0;
        for(int k=19;r>=l&&k>=0;--k){
            if(fail[r][k]>=l)
                ans+=(1<<k),r=fail[r][k];
        }
        cout<<ans+1<<endl;
    }
    return 0;
}

Cut

原文：https://www.cnblogs.com/CADCADCAD/p/14690273.html