支配点对小记

· · 题解

Part1 前言

曾经的“铃原露露”不是这样的！不过这个还是很有意思的。

区间 [l,r] 满足要求当且仅当 \forall a_x,a_y\in[l,r],a_{\operatorname{lca}(x,y)}\in[l,r]。

题意要求一个区间内满足要求的子区间个数。

Part2 思路转换

求 LCA 满足性质的方式就是 dsu on tree 形式的支配点对，与距离相关的则是更常用点分治，本题自然是使用 dsu on tree。

我们可以先只判断单个区间是否满足要求，这时可以尝试使用扫描线，扫右端点。

考虑一个点对 (x,y,z) 其中 z=\operatorname{lca}(x,y),a_x\le a_y：

然而，不合法的区间一定是形如包含 a_x,a_y 而不包含 a_z 的，所以，我们在 dsu on tree 时只需要考虑寻找 a_x 的前驱后继，容易发现，这样只会形成 O(n\log n) 个支配点对。

Part3 具体实现

本题形如【模板】扫描线中的线段树，需要区间加求为零的数字个数。

当然，子区间就是单纯的历史和套路。

于是问题变为了区间加区间历史为零数和。

具体地，线段树上每一个节点维护区间最小值和最小值的出现次数。

在加历史和标记时只有当节点最小值为 0 时才会给最小值打标记，下传时也只会传给最小值相同的，此处形似线段树 3。

不知道为什么，突然想要给代码，HNOI2022 Hope Rank High！

struct dat{int l,r;};
vector<dat>gs[N],qr[N];
void add(int a,int b,int c){
    if(!(a&&b&&c))return;
    if(a>b)swap(a,b);
    if(c>b){
        gs[b].push_back({1,a});
        gs[c].push_back({-1,a});
    }if(c<a)
        gs[b].push_back({c+1,a});
}
void dfs(int x){
    rev[dfn[x]=++dlt]=x;
    for(int y=hd[x];y;y=to[y])dfs(y);
    low[x]=dlt;
}
void dfs(int x,int tp){
    int i,y,z;
    if(lc[x]){
        for(int p=hd[x];p;p=to[p])
            if(p!=lc[x])dfs(p,1);
        dfs(lc[x],0);
        for(int p=hd[x];p;p=to[p])
            if(p!=lc[x]){
                for(i=dfn[p];i<=low[p];++i){
                    y=a[rev[i]];
                    z=G.pre(y),add(y,z,a[x]);
                    z=G.nxt(y),add(y,z,a[x]);
                }for(i=dfn[p];i<=low[p];++i)
                    G.insert(a[rev[i]]);
            }
    }
    if(tp)for(i=dfn[x]+1;i<=low[x];++i)G.erase(a[rev[i]]);
    else G.insert(a[x]);
}
#define ls x<<1
#define rs x<<1|1
const int T=567890;
int mn[T],t1[T],t2[T],ct[T];
ll sm[T],ans[N];
void build(int x,int l,int r){
    ct[x]=r-l+1;
    if(l<r){
        int md=l+r>>1;
        build(ls,l,md);
        build(rs,md+1,r);
    }
}
void at1(int x,int d){t1[x]+=d,mn[x]+=d;}
void at2(int x,int d){
    sm[x]+=ll(d)*ct[x],t2[x]+=d;
}
void pd(int x){
    if(t1[x])at1(ls,t1[x]),at1(rs,t1[x]),t1[x]=0;
    if(t2[x]){
        if(mn[x]==mn[ls])at2(ls,t2[x]);
        if(mn[x]==mn[rs])at2(rs,t2[x]);t2[x]=0;
    }
}void pp(int x){
    mn[x]=mn[ls]<mn[rs]?mn[ls]:mn[rs],sm[x]=sm[ls]+sm[rs];
    ct[x]=(mn[x]==mn[ls]?ct[ls]:0)+(mn[x]==mn[rs]?ct[rs]:0);
}
void cg1(int x,int l,int r,int L,int R,int d){
    if(l>=L&&r<=R)return at1(x,d);
    int md=l+r>>1;pd(x);
    if(L<=md)cg1(ls,l,md,L,R,d);
    if(md<R)cg1(rs,md+1,r,L,R,d);pp(x);
}
void cg2(int x,int l,int r,int L,int R,int d){
    if(l>=L&&r<=R){
        if(!mn[x])at2(x,d);return;
    }int md=l+r>>1;pd(x);
    if(L<=md)cg2(ls,l,md,L,R,d);
    if(md<R)cg2(rs,md+1,r,L,R,d);pp(x);
}
ll qry(int x,int l,int r,int L,int R){
    if(l>=L&&r<=R)return sm[x];pd(x);
    int md=l+r>>1;ll res=0;
    if(L<=md)res+=qry(ls,l,md,L,R);
    if(md<R)res+=qry(rs,md+1,r,L,R);
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int i,j,k,l,r,x,y;
    for(x=1;x<=n;++x)cin>>a[x],sz[x]=1;
    for(x=2;x<=n;++x)cin>>f[x];
    for(x=n;x>1;--x){
        sz[f[x]]+=sz[x];
        sz[lc[f[x]]]<sz[x]&&(lc[f[x]]=x);
        to[x]=hd[f[x]],hd[f[x]]=x;
    }dfs(1),dfs(1,1);
    for(i=1;i<=m;++i)
        cin>>l>>r,qr[r].push_back({l,i});
    build(1,1,n);
    for(x=1;x<=n;++x){
        for(dat at:gs[x])
            if(at.l>0)cg1(1,1,n,at.l,at.r,1);
            else cg1(1,1,n,-at.l,at.r,-1);
        cg2(1,1,n,1,x,1);
        for(dat at:qr[x])
            ans[at.r]=qry(1,1,n,at.l,x);
    }
    for(i=1;i<=m;++i)
        printf("%lld\n",ans[i]);
    return 0;
}