solution - P12018

littlebug · 2025-11-21 20:58:55 · 题解

乱序模拟赛把这个放 D，痛失 AC /ll

画个图出来什么结论都有了啊。

首先注意到一个终点对应的起点一定是一段连续的区间。考虑从左往右递推，只关心每个特殊格子对应的起点区间，就可以证明。

然后从左往右递推一下求出来每个终点的覆盖范围，查询直接倍增就做完了喵。

具体地，在求出每个终点的覆盖范围之后，先求出对于每个区间左端点 l，对应的最大的 r，满足 [l,r] 内所有起点都可以走到同一个终点，然后再倍增处理出从 l 开始 2^j 个区间能到达的最大 r，就可以 O(\log) 查询了。

代码：

// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

int n,m,a[N],f[N][18],Q;
pii g[N<<1];
vector <int> b[N];
bitset <N<<1> bk;

il void solve()
{
    read(n,m),_::r(a,m);

    {
        rep(i,0,n+1) b[i].pb(i+m+1);
        rpe(i,m,1) b[a[i]].pb(i);
        rep(i,0,n+1) bk[b[i].back()]=1;

        auto upd=[](pii& a,const pii& b){chmin(a.st,b.st),chmax(a.nd,b.nd);};

        rep(i,0,m+n+2) g[i]={inf,-inf};
        rep(i,1,m)
        {
            b[a[i]].pop_back();
            bk[i]&&(upd(g[i],{a[i],a[i]}),1);
            upd(g[b[a[i]-1].back()],g[i]),upd(g[b[a[i]+1].back()],g[i]);
        }
        rep(i,0,n+1) bk[i+m+1]&&(upd(g[i+m+1],{i,i}),1);
    }

    {
        rep(i,0,n+1) g[i+m+1].nd>0 && (f[g[i+m+1].st][0]=g[i+m+1].nd+1);
        rep(i,1,n+1) chmin(chmax(f[i][0],f[i-1][0]),n+1);
        rep(j,1,17) rep(i,0,n+1) f[i][j]=f[f[i][j-1]][j-1];
    }

    read(Q); int l,r,ans;
    while(Q--)
    {
        read(l,r);
        ans=0;
        rpe(j,17,0) f[l][j]<=r&&(ans+=1<<j,l=f[l][j]);
        write(ans+1,'\n');
    }
}

华风夏韵，洛水天依！