P11364 [NOIP2024] 树上查询

mskqwq · 2024-11-30 17:38:53 · 题解

纪念这场把我创飞的 NOIP，为什么考场上写那么久还写不出来呢？

baka。

做过 P7880 应该很容易想到离线然后使用树上启发式合并预处理。设当前遍历到了点 u，对于所有 u 轻子树中的结点 x，我们希望知道两个 p,q 使得 x \in [p,q]，且 [p,q] 中的点都在 u 子树内，当然 p 要尽量小，q 要尽量大。于是 x 的贡献就可以写成 (p,q,dep_u) 这样的形势，对于一组询问 (l,r,k)，如果 [l,r] \cap [p,q] 的大小 \ge k，那么就有 dep_u 的贡献。

如何找出所有的 (p,q,dep_u)？考虑二分，我们需要知道一段区间内的数的 dfs 序的最大和最小值，以便判断这些数是否都在 u 子树内，st 表预处理即可。

然后处理询问，通过分讨交在左边，交在右边，以及包含的情况，不难发现限制是一个二维偏序，简单处理即可。

这样做时间复杂度是 O(n \log^2 n)，不够优秀，尝试优化寻找三元组的部分。发现本质不同的 [p,q] 连续段实际上只有 O(n) 个，因为它一定是由若干个小的连续段拼起来的。考虑用并查集代替二分，记 pre_x 和 nxt_x 表示 x 所在的连续段的左右端点，合并两段时并查集维护即可。

不算并查集的话复杂度 O(n\log n)，本地拍了几千组小数据，极限数据 2.5s。瓶颈在二维偏序，启发式合并只花了 0.6s，应该是线段树太慢了，被卡常再改吧。

upd：云斗上过了，应该没事。

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <ctime>
#include <cstdio>
#include <random>
#include <vector>
#include <bitset>
#include <cassert>
#include <cstring>
#include <algorithm>
#define fi first
#define se second
#define MISAKA main
#define ll long long
#define eb emplace_back
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rep(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define FIO(FILE) freopen(FILE".in","r",stdin),freopen(FILE".out","w",stdout)
using namespace std;
bool __st;
inline int read(){
    char ch=getchar();int f=1,x=0;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=5e5+10,mod=998244353;
int n,q,dfn[N],id[N],siz[N],tim,son[N],dep[N],ans[N],nxt[N],pre[N];
vector<int> g[N];set<int> s;
struct node{int x,y,k,id;
    node(int a=0,int b=0,int c=0,int d=0){x=a,y=b,k=c,id=d;}
};vector<node> v1,v2;
bool cmp(node a,node b){return a.k>b.k;}
vector<pii> Q[N],v[N];
int gn(int x){return nxt[x]=x==nxt[x]?x:gn(nxt[x]);}
int gp(int x){return pre[x]=x==pre[x]?x:gp(pre[x]);}
void solve(int x,int L,int R,int d){
    int p=gp(x),q=gn(x),flag=0;
    while(L<=dfn[q+1]&&dfn[q+1]<=R) nxt[q]=q+1,pre[q+1]=q,q=gn(q+1),flag=1;
    while(L<=dfn[p-1]&&dfn[p-1]<=R) pre[p]=p-1,nxt[p-1]=p,p=gp(p-1),flag=1;
    if(flag) v1.eb(p,q,q-p+1,d),v[q].eb(p,d);
}
void dfs(int u,int f){
    dep[u]=dep[f]+1,siz[u]=1;id[dfn[u]=++tim]=u;
    for(int v:g[u])if(v!=f){
        dfs(v,u),siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs(int u,int f,int tp){
    for(int v:g[u])if(v!=f&&v!=son[u]) dfs(v,u,0);
    if(son[u]) dfs(son[u],u,1);
    for(int v:g[u])if(v!=f&&v!=son[u])
        rep(i,dfn[v],dfn[v]+siz[v]-1) 
            solve(id[i],dfn[u],dfn[u]+siz[u]-1,dep[u]);
    solve(u,dfn[u],dfn[u]+siz[u]-1,dep[u]);
}
struct segtree{int l,r,mx;}t[N<<2];
void bd(int x,int l,int r){
    t[x]={l,r,0};int mid=l+r>>1;
    if(l^r) bd(2*x,l,mid),bd(2*x+1,mid+1,r);
}
void upd(int x,int p,int k){
    t[x].mx=max(t[x].mx,k);
    if(t[x].l^t[x].r) upd(2*x+(p>t[2*x].r),p,k);
}
int qry(int x,int l,int r){
    if(t[x].r<l||t[x].l>r) return 0;
    if(l<=t[x].l&&t[x].r<=r) return t[x].mx;
    return max(qry(2*x,l,r),qry(2*x+1,l,r));
}
void misaka(){
    n=read();
    rep(i,2,n){
        int u=read(),v=read();
        g[u].eb(v);g[v].eb(u);
    }
    dfs(1,0);
    rep(i,1,n) pre[i]=i,nxt[i]=i,v1.eb(i,i,1,dep[i]);
    dfs(1,0,1);q=read();
    rep(i,1,q){
        int l=read(),r=read(),k=read();
        Q[r].eb(l,i);v2.eb(l,r,k,i);
    }
    sort(v1.begin(),v1.end(),cmp);
    sort(v2.begin(),v2.end(),cmp);
    bd(1,1,n);
    int j=0;rep(i,0,v2.size()-1){
        while(j<v1.size()&&v1[j].k>=v2[i].k) 
            upd(1,v1[j].y,v1[j].id),j++;
        int id=v2[i].id,l=v2[i].x+v2[i].k-1,r=v2[i].y;
        ans[id]=max(ans[id],qry(1,l,r));
    }
    bd(1,1,n);
    j=0;rep(i,0,v2.size()-1){
        while(j<v1.size()&&v1[j].k>=v2[i].k) 
            upd(1,v1[j].x,v1[j].id),j++;
        int id=v2[i].id,l=v2[i].x,r=v2[i].y-v2[i].k+1;
        ans[id]=max(ans[id],qry(1,l,r));
    }
    bd(1,1,n);
    _rep(i,n,1){
        for(auto [x,y]:v[i]) upd(1,x,y);
        for(auto [x,y]:Q[i]) ans[y]=max(ans[y],qry(1,1,x));
    }
    rep(i,1,q) printf("%d\n",ans[i]);
}
bool __ed;
signed MISAKA(){
    #ifdef LOCAL_MSK
    atexit([](){
    debug("\n%.3lfs ",(double)clock()/CLOCKS_PER_SEC);
    debug("%.3lfMB",abs(&__st-&__ed)/1024./1024);});
    #endif
    int T=1;
    while(T--) misaka();
    return 0;
}