本来能让我翻盘上 Ag 线的，但是不会树状数组上二分导致被卡常，遂翻盘失败。
考虑 Prüfer 序列转树的过程是对每个 $i$ 选取最小的 $i$ 往后没有出现且之前没有作为这个数连边的数和当前位置连边，最后剩下的两个连边。
于是我们考虑求出来 $x,y$ 分别在什么地方作为没有出现的那个数，然后判一下这个位置是不是另一个位置或者这两个是否恰好是最后两个即可。
那么考虑每个 $i$ 选取最小的 $i$ 往后没有出现的数怎么刻画，实际上如果 $x$ 满足要求那么容易有比 $x$ 小的没有出现的数的个数恰为 $i-1$。
而且由于 $i$ 每 $+1$，最多新增一个没有出现的数。
于是对于每个 $x$ 只要其已经作为没有出现的那个数链边了，那么就一定满足比其小的没有出现的数个数不超过 $i-1$。
并且 $x$ 出现的时间显然是前缀。
然后就可以对于 $i$ 二分了。
在二分内部需要做的就是判断 $x$ 是否出现以及对满足如下条件的数计数。

其中 $\mathrm{nxt}_t$ 表示 $a_t$ 下一次出现的位置。
那么我们在二分外对 $a_t<x$ 这个要求扫描线之后就可以用树套树维护了。
复杂度是 $O(n\log^3n)$ 显然过不去，考虑优化。
我们把 $l\le t\le i$ 提到外层线段树维护。
然后对于 $x$ 未出现的条件先用一个二分额外维护了找到核心二分的下界。
然后就可以使用线段树上二分做到 $O(n\log^2n)$ 了，可能会卡常，把线段树二分换成树状数组二分即可。
:::info[代码]

#include "kapok.h"
#include <bits/stdc++.h>
using namespace std;

struct node
{
    int Ls,Rs,tot;
}seg[40000005];

int cnt,rt[200005],ans[400005],a[200005];
vector<array<int,4>>q[200005];
vector<int>vec[200005];

void add(int&u,int x,int l,int r)
{
    if(!u)
        u=++cnt,
        seg[u]={0,0,0};
    ++seg[u].tot;
    if(l==r)
        return;
    int mid=l+r>>1;
    if(x<=mid)
        add(seg[u].Ls,x,l,mid);
    else
        add(seg[u].Rs,x,mid+1,r);
}

int query(int u,int ql,int qr,int l,int r)
{
    if(!u||ql>r||qr<l)
        return 0;
    if(ql<=l&&r<=qr)
        return seg[u].tot;
    int mid=l+r>>1;
    return query(seg[u].Ls,ql,qr,l,mid)+query(seg[u].Rs,ql,qr,mid+1,r);
}

void add(int p,int nxt,int n)
{
    for(int i=p;i<=n+1;i+=i&-i)
        add(rt[i],nxt,1,n+2);
}

int query(int p,int nxt,int n)
{
    int sum=0;
    for(int i=p;i>0;i-=i&-i)
        sum+=query(rt[i],nxt,n+2,1,n+2);
    return sum;
}

vector<bool>kapok(int c,int n,int m,vector<int>a,vector<int>l,vector<int>r,vector<int>x,vector<int>y)
{
    cnt=0;
    for(int i=0;i<n;i++)
        ::a[i]=a[i];
    for(int i=0;i<=n+1;i++)
        rt[i]=0,
        vec[i].clear(),
        q[i].clear();
    for(int i=0;i<n;i++)
        vec[a[i]].push_back(i);
    for(int i=0;i<m;i++)
    {
        int s=r[i]-l[i]+2;
        if(x[i]==s-1)
            ans[i<<1]=s-2;
        else
            q[x[i]].push_back({l[i],r[i],x[i],i<<1});
        if(y[i]==s-1)
            ans[i<<1|1]=s-2;
        else
            q[y[i]].push_back({l[i],r[i],y[i],i<<1|1});
    }
    for(int i=0;i<=n+1;i++)
    {
        for(int u=0;u<vec[i].size();u++)
            add(vec[i][u]+2,((u+1<vec[i].size())?vec[i][u+1]:n)+2,n);
        for(auto&[l,r,x,t]:q[i])
        {
            int lst=-1;
            auto it=upper_bound(vec[x].begin(),vec[x].end(),r-1);
            if(it!=vec[x].begin())
                lst=*prev(it);
            int now=x+1+l-query(r+1,r+2,n),u=0,v=0;
            for(int y=1<<18;y>0;y>>=1)
                if(u+y<=n+1)
                {
                    int tmp=query(rt[u+y],r+2,n+2,1,n+2);
                    if(u+y-v-tmp<now)
                        u=u+y,
                        v+=tmp;
                }
            ans[t]=max(lst-l+1,u-l);
        }
    }
    vector<bool>Ans(m,0);
    for(int i=0;i<m;i++)
    {
        if(x[i]==y[i])
            continue;
        int s=r[i]-l[i]+2,flag=0;
        int u=ans[i<<1];
        int v=ans[i<<1|1];
        if(u<s-2)
            flag|=min(s-1,a[l[i]+u])==y[i];
        if(v<s-2)
            flag|=min(s-1,a[l[i]+v])==x[i];
        flag|=u>=s-2&&v>=s-2;
        Ans[i]=flag;
    }
    return Ans;
}

:::