题解：P17144 [NOI 2026] 木棉（暂无数据）

SDSXC · 2026-07-24 22:14:20 · 题解

感觉比 D2T1 简单很多。

考虑假设已知一个 Prufer 序列如何确定原树。首先我们知道，这个删除过程结束之后剩下的节点里面的其中一个一定为 n 号节点，所以不妨把它作为原树的根。考虑没有在序列中出现的树都是原树的叶子，先把他们加入进叶子集合中。然后从前往后扫描 Prufer 序列，每次从叶子集合中选出最小的，显然这步操作被删除的就是这个叶子，于是成功找到了它的父亲，把这个叶子从叶子集合中删除，如果它的父亲在后面的 Prufer 序列中没有出现过，那么加入叶子集合。所有操作结束之后最后叶子集合还会剩下一个点，把它和 n 连上。

于是模拟上述过程，开一个堆来维护叶子集合，即可做到 O(nq\log n)。精细实现可以做到 O(nq) 但是与正解关系不大。

回到原题，显然 x,y 相邻等价于 x 是 y 的父亲或 y 是 x 的父亲。如果 y 是 x 的父亲，那么相当于 x 被从堆中弹出的时候，扫描到原序列位置恰好为一个 y。考虑如何快速找到 x 被从堆中弹出的位置。

令 lst_x 表示 x 在 [l,r] 中最后一次出现的位置，x 在 lst_x 处被加入堆中，令 cnt 表示堆中 <x 的数的个数。显然 x 在 i 的位置被弹出等价于 i>lst_x，且 i 是最小的满足扫描到 i 处时 cnt=0 的位置。

分析一下 cnt 是如何变化的。初始被赋值为 lst_t<l 且 t<x 的 t 的个数。每个位置上，如果 a_i<x 且 lst_{a_i}=i，那么 cnt\gets cnt+1。然后堆中弹出一个数，cnt\gets cnt-1。如果变成了 cnt<0 并且 x 已经被添加到堆中，那么相当于弹出 x，结束这个过程，如果 x 没有被添加到堆中，那么由于这个过程中 cnt 单调不增，x 被加入时 cnt 也一定为 0，所以 x 会在加入后的下一轮立即弹出，简单特判一下即可。

因为 cnt 单调不增，所以可以考虑二分这个 cnt=0 的位置，然后用一些数据结构维护。

因为过程和 lst 比较相关，所以考虑对 r 扫描线，这样 lst 就容易维护了。然后有 O(n) 次对 lst 的修改。

二分时，每次 check 操作 [l,r] 之后 cnt 变成多少。减少量显然是 r-l+1，增加量相当于查询 i\in [l,r] 中 a_i<x 且 lst_{a_i}=i 的位置个数，容易树套树维护。

树套树 \log^2 n，二分 \log n，于是一次询问 \log^3 n，显然太慢了。考虑优化，把树套树的下标维度放在外层维护，这样就可以把二分和外层线段树放在一起用线段树上二分搞定。同时注意到每颗内层数插入的数的值域离散化之后只有 O(sz)，所以不需要平衡树可以直接使用树状数组。于是得到一个比较好写的 O((n+q)\log ^2n) 做法。

代码：

#include"kapok.h"
#include<bits/stdc++.h>
#define N 200009
#define ls (rt<<1)
#define rs (rt<<1|1)
#define pb push_back
using namespace std;
struct node{
    vector<int> a,c;int sz;
    void init(vector<int> &aa){
        a=aa;sort(a.begin(),a.end());
        a.resize(sz=unique(a.begin(),a.end())-a.begin());
        c.assign(sz+1,0);
    }
    void upd(int x,int v){
        x=lower_bound(a.begin(),a.end(),x)-a.begin()+1;
        for(;x<=sz;x+=(x&-x))c[x]+=v;
    }
    int qry(int x){
        x=lower_bound(a.begin(),a.end(),x)-a.begin();
        int v=0;for(;x;x-=(x&-x))v+=c[x];return v;
    }
} TT;
vector<int> a;int n;
vector<array<int,4>> Q[N];
int lst[N];
struct SGT{
    node tr[N<<2];
    void build(int rt,int l,int r){
        vector<int> b(r-l+1);
        for(int i=l;i<=r;i++)b[i-l]=a[i];
        tr[rt].init(b);
        if(l^r){
            int mid=l+r>>1;
            build(ls,l,mid);build(rs,mid+1,r);
        }
    }
    void upd(int rt,int l,int r,int x,int v){
        tr[rt].upd(a[x],v);
        if(l^r){
            int mid=l+r>>1;
            if(x<=mid)upd(ls,l,mid,x,v);
            else upd(rs,mid+1,r,x,v);
        }
    }
    int q1(int rt,int l,int r,int ql,int qr,int x){
        if(ql>r||qr<l)return 0;
        else if(ql<=l&&qr>=r)return tr[rt].qry(x);
        else{
            int mid=l+r>>1;
            return q1(ls,l,mid,ql,qr,x)+q1(rs,mid+1,r,ql,qr,x);
        }
    }
    int q2(int rt,int l,int r,int ql,int qr,int x,int &y){
        if(ql>r||qr<l)return n;
        else if(ql<=l&&qr>=r){
            int s=tr[rt].qry(x),t=r-l+1;
            if(y+s-t>0){y+=s-t;return n;}
        }
        if(l==r)return l;
        int mid=l+r>>1,L=q2(ls,l,mid,ql,qr,x,y);
        return (L<=r)?L:q2(rs,mid+1,r,ql,qr,x,y);
    }
} T;
vector<bool> kapok(int C,int n,int q,vector<int> a,vector<int> l,vector<int> r,vector<int> x,vector<int> y){
    ::n=n;::a=a;T.build(1,0,n-1);TT.init(a);
    vector<bool> ans(q,0);memset(lst,-1,sizeof(lst));
    for(int i=0;i<q;i++){
        if(x[i]==y[i])continue;
        if(l[i]==r[i]){ans[i]=1;continue;}
        int t=r[i]-l[i]+1;
        if(x[i]!=t)Q[r[i]-1].pb({l[i],x[i],y[i],i});
        if(y[i]!=t)Q[r[i]-1].pb({l[i],y[i],x[i],i});
    }
    for(int r=0;r<n;r++){
        if(~lst[a[r]])T.upd(1,0,n-1,lst[a[r]],-1);
        else TT.upd(a[r],1);
        lst[a[r]]=r;T.upd(1,0,n-1,r,1);
        for(auto [l,x,y,id]:Q[r]){
            if(y!=r-l+2&&lst[x]>lst[y])continue;
            int cnt=x-TT.qry(x)+T.q1(1,0,n-1,0,max(l-1,lst[x]),x)-max(0,lst[x]-l+1);
            int t=(cnt<=0||lst[x]>=r)?max(lst[x]+1,l):T.q2(1,0,n-1,max(lst[x]+1,l),r,x,cnt)+1;
            ans[id]=(y==((t>r)?r-l+2:min(r-l+2,a[t])));
        }
    }
    return ans;
}