NOIP2024 树上查询题解

来一个考场做法和后续优化。

首先有一个

O(1)

求 lca 的前置知识：我们在 dfs 序上考虑，设求点

x,y

（

x\neq y

）的 lca，不妨设

dfn_x<dfn_y

，则 lca 为

[dfn_x+1,dfn_y]

区间上深度最小的点的父亲。手玩一下就可以证明了。

可以发现多个点的 lca 是可合并可重信息，于是可以用 st 表维护区间 lca。

于是可以得到一个

O(nq)

的暴力，由于只要考虑长度恰好等于

k

的区间，我们枚举

O(n)

个区间，然后求出 lca，比较即可。可以获得

32

的好成绩。

看到剩下的除了正解就是链了，于是考虑链。我们不妨直接把链考虑成序列：

a_i

表示点

i

的深度。则询问相当于最大化子区间内所有长度

\ge k

的区间的

\max

。一个直接的想法是二分答案

x

，则我们把值

\ge x

的称为可行点，其它称为断点。注意到除了包含区间边界的时候，只有极长的可行点区间是有用的。即区间

[l,r]

有用当且仅当

\min^r_{i=l}a_i\ge x

且

a_{l-1}<x

，

a_{r+1}<x

。其余只需要考虑特判区间

[L,L+k-1]

和

[R-k+1,R]

即可（

L,R,k

为题面中的询问参数）。

这种区间一看就非常符合直觉，看上去非常有优化前途啊！我们不妨设

a_{l-1}\ge a_{r+1}

，则可以发现

[l,r]

的所有数都

>a_{l-1}

，则

a_{r+1}

是

l-1

右边的第一个

\le a_{l-1}

的；同理，当

a_{l-1}\le a_{r+1}

时，

a_{l-1}

是

a_{r+1}

左边第一个更小的。也就是说，最多只有这样

2n

个区间是有用的。

朴素做，对于一个有用区间

(l,r,x)

，其中

x

表示

[l,r]

区间的 lca 深度，则要求

l\ge L

，

r\le R

，

r-l+1\ge k

。这就是三维数点板子了，我们里先后随便找一维排序，然后用树套树解决。时间复杂度

O((n+q)\log^2n)

，使用线段树套 treap 空间复杂度

O((n+q)\log n)

。考场上我花了半小时实现了该做法（虽然还调了半小时），期望得分最好有

64

。

考虑是否可以扩展到树上。注意到链可做的原因是，lca 可以表示为区间

\min

。我们脑洞大开，用前置知识中

O(1)

lca 来考虑。在 dfn 序列中，区间 lca 相当于钦定了若干单点（区间内所有点的 dfn 序），然后求所有点形成的左开右闭区间的

\min

的最小值，可以发现就是 dfn 序列上最大最小值区间的最小值。同时考虑这个拆法，为了模仿链的做法，我们也类似地把这个大区间拆成若干个小区间的并，其中每个小区间是原序列中相邻两点在 dfn 序列上表示的左开右闭区间。也就是说，令

a_i

表示

\min^{\max(dfn_i,dfn_{i+1})}_{j=\min(dfn_i,dfn_{i+1})+1}dep_j-1

，则区间 lca 的深度即为

\min^{r-1}_{i=l}a_i

，因为这些小区间一定能覆盖整个大区间。也就是说我们在令

a_i

为

dep_{lca(i,i+1)}

时可以用和链一样的做法做，即找到

2n

个有用区间尝试。注意这个做法需要特判

k=1

。时间复杂度

O((n+q)\log^2n)

，不知道能不能过，感觉常数不大。

zhuzhu2891 告诉我每个区间只需要保留前后缀即可。具体地，在三维偏序的

l,r,len

三个限制中，我们分别只考虑

l,len

和

r,len

的限制，令新区间被原区间包含即可。从刚才二分答案的角度思考可以感性理解只保留前后缀的正确性。注意到虽然长度缩小后区间

\min

可能会改变，但是按原来的值算只会更劣，一定会被更优的区间前后缀覆盖，所以这个做法可以仅用二维偏序实现，按

len

排序之后实现单点修改区间求

\max

即可。时间复杂度

O((n+q)\log n)

。

CPP

#include<bits/stdc++.h>
#define REP(i,a,n) for(int i=(a);i<(int)(n);++i)
#define pb push_back
using namespace std;
int read(){
	int res=0;char c=getchar();
	while(c<48||c>57)c=getchar();
	do res=(res<<1)+(res<<3)+(c^48),c=getchar();while(c>=48&&c<=57);
	return res;
}
struct queries{
    int l,r,id;
};
struct ds{
    int seg[2000005];
    void build(int l,int r,int p){
        seg[p]=0;
        if(l==r)return;
        int m=(l+r)>>1;
        build(l,m,p*2+1);build(m+1,r,p*2+2);
    }
    void update(int pos,int l,int r,int p,int val){
        seg[p]=max(seg[p],val);
        if(l==r)return;
        int m=(l+r)>>1;
        if(m>=pos)update(pos,l,m,p*2+1,val);
        else update(pos,m+1,r,p*2+2,val);
    }
    int query(int l,int r,int s,int t,int p){
        if(l<=s&&t<=r)return seg[p];
        int m=(s+t)>>1,res=0;
        if(m>=l)res=query(l,r,s,m,p*2+1);
        if(m<r)res=max(res,query(l,r,m+1,t,p*2+2));
        return res;
    }
}s1,s2;
int n,q;
vector<int>v[500005];
int an[22][500005],fa[500005],dep[500005],a[500005];
int st[22][500005],mx[22][500005],dfn[500005];
int tot;
int ans[500005];
vector<queries>qr[500005],add[500005];
int getmax(int x,int y){return dep[x]<dep[y]? x:y;}
void dfs(int x,int pre,int d){
	fa[x]=pre;dfn[x]=tot++;an[0][dfn[x]]=pre;dep[x]=d;
	for(auto i:v[x])if(i!=pre)dfs(i,x,d+1);
}
int getlca(int x,int y){
	if(x==y)return x;
	x=dfn[x];y=dfn[y];if(x>y)swap(x,y);
	int s=__lg(y-x);
	return getmax(an[s][x+1],an[s][y-(1<<s)+1]);
}
int query(int l,int r){
	int s=__lg(r-l+1);
    return dep[getlca(st[s][l],st[s][r-(1<<s)+1])]+1;
}
int qmax(int l,int r){
    int s=__lg(r-l+1);
    return max(mx[s][l],mx[s][r-(1<<s)+1]);
}
signed main(){
	freopen("query.in","r",stdin);
	freopen("query.out","w",stdout);
	n=read();
	REP(i,1,n){
		int x=read()-1,y=read()-1;
		v[x].pb(y);v[y].pb(x);
	}
	dfs(0,-1,0);
	REP(j,0,__lg(n-1)){
		REP(i,1,n-(1<<(j+1))+1)an[j+1][i]=getmax(an[j][i],an[j][i+(1<<j)]);
	}
	REP(i,0,n)st[0][i]=i,mx[0][i]=dep[i]+1;
	REP(j,0,__lg(n)){
		REP(i,0,n-(1<<(j+1))+1)st[j+1][i]=getlca(st[j][i],st[j][i+(1<<j)]);
		REP(i,0,n-(1<<(j+1))+1)mx[j+1][i]=max(mx[j][i],mx[j][i+(1<<j)]);
	}
    REP(i,0,n-1)a[i]=dep[getlca(i,i+1)];
    stack<int>st;
    REP(i,0,n-1){
        while(!st.empty()&&a[st.top()]>a[i])st.pop();
        if(!st.empty()){
            int x=st.top()+1;
            if(x<i){
                queries y={x,i-1,query(x,i)};
                add[i-x].pb(y);
            }
        }
        st.push(i);
    }
    while(!st.empty())st.pop();
    for(int i=n-2;i>=0;--i){
        while(!st.empty()&&a[st.top()]>a[i])st.pop();
        if(!st.empty()){
            int x=st.top()-1;
            if(x>i){
                queries y={i+1,x,query(i+1,x+1)};
                add[x-i].pb(y);
            }
        }
        st.push(i);
    }
    q=read();
    REP(i,0,q){
        int l=read()-1,r=read()-1,k=read();
        if(k==1)ans[i]=qmax(l,r);
        else{
        	ans[i]=max(query(l,l+k-1),query(r-k+1,r));
            --r;--k;
            qr[k].pb({l,r,i});
        }
    }
    --n;
    s1.build(0,n-1,0);s2.build(0,n-1,0);
    for(int i=n;i>=1;--i){
        for(auto j:add[i]){
            s1.update(j.l,0,n-1,0,j.id);
            s2.update(j.r,0,n-1,0,j.id);
        }
        for(auto j:qr[i]){
            ans[j.id]=max(ans[j.id],s1.query(j.l,j.r-i+1,0,n-1,0));
            ans[j.id]=max(ans[j.id],s2.query(j.l+i-1,j.r,0,n-1,0));
        }
    }
    REP(i,0,q)cout<<ans[i]<<"\n";
    cerr<<clock()<<endl;
	return 0;
}

NOIP2024 树上查询题解

文章操作

相关推荐

评论

NOIP2024 树上查询题解