CF2152F Triple Attack 题解

huangleyi0129 · 2025-10-04 21:22:26 · 题解

注意到答案按奇偶位置可以划为两个序列，相邻位置差 >z。

而任意两个这样的不交序列一定可以可以拼成答案，充要性易证，而选择 (l,l+1) 作为两序列开头是不劣的。

而一个位置贪心的跳时，后继是唯一的，使用树刻画该结构，则易知 (i,i+1) 贪心跳跃首次交在 w=\operatorname{LCA}(i,i+1) 处，此时取一个跳到 w+1 处即可归约到 (w,w+1)，倍增处理这种跳跃即可，时间复杂度 O((n+q)\log n)。

为什么我赛时写的这么不牛呢，代码如下（没用 LCA，而是大力分段讨论，非常不美）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=250005;
int a[N],fa[N][23],fa2[N][23],c[N][23],p[N],d[N],n,q,z,K,t;
int query(int l,int r)
{
    int u,v,s;
    s=2;
    for(int i=K; i>=0; --i)
        if(fa2[l][i]<=r)
            s+=c[l][i],l=fa2[l][i];
    if(l==r)
        --s;
    else
    {
        u=l,v=l+1;
        for(int i=K; i>=0; --i)
            if(fa[u][i]<=r)
                s+=1<<i,u=fa[u][i];
        for(int i=K; i>=0; --i)
            if(fa[v][i]<=r)
                s+=1<<i,v=fa[v][i];
    }
    return s;
}
void solve()
{
    int u,v,l,r,s;
    cin>>n>>z,K=__lg(n);
    for(int i=1; i<=n; ++i)
        cin>>a[i];
    for(int i=1; i<=n; ++i)
        fa[i][0]=upper_bound(a+1,a+1+n,a[i]+z)-a;
    fa[n+1][0]=n+1;
    for(int j=1; j<=K; ++j)
        for(int i=1; i<=n+1; ++i)
            fa[i][j]=fa[fa[i][j-1]][j-1];
    p[t=1]=1;
    for(int i=1; i<n; ++i)
        if(a[i+1]-a[i]<=z)
        {
            l=i,r=i+1,u=0;
            for(int j=K; j>=0; --j)
                if(fa[l][j]!=fa[r][j])
                    l=fa[l][j],r=fa[r][j],u+=1<<j;
            if(fa[l][0]==fa[r][0]&&fa[l][0]<=n)
                c[i][0]=u+1<<1,fa2[i][0]=fa[l][0];
            else
            {
                l=i+1,r=fa[i][0],u=1;
                for(int j=K; j>=0; --j)
                    if(fa[l][j]!=fa[r][j])
                        l=fa[l][j],r=fa[r][j],u+=1<<j+1;
                if(fa[l][0]==fa[r][0]&&fa[l][0]<=n)
                    c[i][0]=u+2,fa2[i][0]=fa[l][0];
                else
                    c[i][0]=0,fa2[i][0]=n+1;
            }
        }
        else
            fa2[i][0]=n+1,p[++t]=i+1;
    fa2[n][0]=n+1;
    p[++t]=n+1;
    fa2[n+1][0]=n+1;
    for(int j=1; j<=K; ++j)
        for(int i=1; i<=n+1; ++i)
            fa2[i][j]=fa2[fa2[i][j-1]][j-1],c[i][j]=c[i][j-1]+c[fa2[i][j-1]][j-1];
    for(int i=1; i<t; ++i)
        d[i]=d[i-1]+query(p[i],p[i+1]-1);
    cin>>q;
    while(q--)
    {
        cin>>l>>r;
        u=upper_bound(p+1,p+1+t,l)-p,v=upper_bound(p+1,p+1+t,r)-p-1;
        if(u>v)
            s=query(l,r);
        else
            s=d[v-1]-d[u-1]+query(l,p[u]-1)+query(p[v],r);
        cout<<s<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}