NOIP2024 T4 题解

· · 题解

题目大意

n$ 个点的树，$q$ 此询问 $l,r,k$，求 $\max\limits_{l\leq l' \leq r' \leq r,r'-l'+1 \geq k}{dep_{\operatorname{lca}\{l',l'+1,\dots,r'\}}} n,q \leq 5\times 10^5

题目分析

首先一定有 r'-l'+1=k，因为不劣。然后考虑真正有用的区间大概成一个树形结构，只有 \mathcal O(n) 个。这部分可以将相邻 \operatorname{lca} 的深度插到堆里，每次取最大的合并？

然后只需要满足有用区间与询问区间的交 \geq k，求权值最大值。

对于有用区间在询问区间右边的情况，可以把权值放到有用区间的左端点，然后区间查询 [l,r-k+1] 的最大值。右边同理。内部再加个有用区间长度 \geq k 的限制。外部直接求全局答案。

二位偏序（长度 \geq k，然后单点修改区间查询）。复杂度单 \log。

代码

只能说退役 4 个月代码能力为 0，场上没时间写了。很遗憾没能 AK。

upd：

#include<bits/stdc++.h>
using namespace std;
using namespace my_std;
ll n,q,m=0,head[500050],cnt=0,dep[500050],f[500050][19];
ll val[500050],st[500050],top=0,lc[500050],rc[500050],L[500050],R[500050];
ll ST[19][500050],lg[500050],ans[500050];
struct edge{
    ll nxt,to;
}e[1000010];
struct node{
    ll l,r,k,v,id;
}p[500050],a[1000010];
struct seg{
    #define LC x<<1
    #define RC x<<1|1
    ll tree[2000020];
    il void pushup(ll x){
        tree[x]=max(tree[LC],tree[RC]);
    }
    void mdf(ll x,ll l,ll r,ll pos,ll v){
        if(l==r){
            tree[x]=max(tree[x],v);
            return;
        }
        ll mid=(l+r)>>1;
        if(pos<=mid) mdf(LC,l,mid,pos,v);
        else mdf(RC,mid+1,r,pos,v);
        pushup(x);
    }
    ll query(ll x,ll l,ll r,ll ql,ll qr){
        if(ql<=l&&r<=qr) return tree[x];
        ll mid=(l+r)>>1,res=0;
        if(ql<=mid) res=max(res,query(LC,l,mid,ql,qr));
        if(mid<qr) res=max(res,query(RC,mid+1,r,ql,qr));
        return res;
    }
}Tl,Tr;
il bl operator<(const node &x,const node &y){
    return x.k>y.k;
}
il void add(ll u,ll v){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
void dfs(ll fa,ll u){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    fr(i,1,18) f[u][i]=f[f[u][i-1]][i-1];
    go(u){
        ll v=e[i].to;
        if(v==fa) continue;
        dfs(u,v);
    }
}
il ll get_lca(ll x,ll y){
    if(dep[x]<dep[y]) swap(x,y);
    pfr(i,18,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    pfr(i,18,0){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
void dfs2(ll x){
    L[x]=x-1;
    R[x]=x;
    if(lc[x]){
        dfs2(lc[x]);
        L[x]=L[lc[x]];
    }
    if(rc[x]){
        dfs2(rc[x]);
        R[x]=R[rc[x]];
    }
}
il ll querymin(ll l,ll r){
    ll tmp=lg[r-l+1];
    return min(ST[tmp][l],ST[tmp][r-(1ll<<tmp)+1]);
}
int main(){
    n=read();
    fr(i,2,n){
        ll u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    dfs(0,1);
    fr(i,2,n) val[i]=get_lca(i-1,i);
    fr(i,2,n){
        ll tmp=top;
        while(tmp&&dep[val[i]]<dep[val[st[tmp]]]) tmp--;
        if(tmp) rc[st[tmp]]=i;
        if(tmp<top) lc[i]=st[tmp+1];
        top=tmp;
        st[++top]=i;
    }
    dfs2(st[1]);
    fr(i,1,n) a[++m]=(node){i,i,1,dep[i],0};
    fr(i,2,n) a[++m]=(node){L[i],R[i],R[i]-L[i]+1,dep[val[i]],0};
    fr(i,2,n) lg[i]=lg[i>>1]+1;
    fr(i,2,n) ST[0][i]=dep[val[i]];
    fr(j,1,18) fr(i,2,n-(1ll<<j)+1) ST[j][i]=min(ST[j-1][i],ST[j-1][i+(1ll<<(j-1))]);
    q=read();
    fr(i,1,q){
        p[i].l=read();
        p[i].r=read();
        p[i].k=read();
        p[i].id=i;
        if(p[i].l==p[i].r) p[i].v=dep[p[i].l];
        else p[i].v=querymin(p[i].l+1,p[i].r);
    }
    sort(p+1,p+q+1);
    sort(a+1,a+m+1);
    ll pos=1;
    fr(i,1,q){
        while(pos<=m&&a[pos].k>=p[i].k){
            Tl.mdf(1,1,n,a[pos].l,a[pos].v);
            Tr.mdf(1,1,n,a[pos].r,a[pos].v);
            pos++;
        }
        p[i].v=max(p[i].v,max(Tl.query(1,1,n,p[i].l,p[i].r-p[i].k+1),Tr.query(1,1,n,p[i].l+p[i].k-1,p[i].r)));
    }
    fr(i,1,q) ans[p[i].id]=p[i].v;
    fr(i,1,q) writeln(ans[i]);
}