题解 | Promotion-牛客假日团队赛4E题

The cows, conveniently numbered , organize the company as a tree, with cow 1 as the president (the root of the tree). Each cow except the president has a single manager (its "parent" in the tree). Each cow i has a distinct proficiency rating, p(i), which describes how good she is at her job. If cow i is an ancestor (e.g., a manager of a manager of a manager) of cow j, then we say j is a subordinate of i.

输入描述:

【数据规模】

问题实质：求树上逆序对

  解法一： 树状数组 / 线段树 + dfs
对能力值开一个权值线段树((范围较大 ，加一个离散化))。

 对于每个节点 ，在线段树中查询数值大于 的数的个数，再对于点 所有儿子节点的权值都进行一次【单点修改】操作，将它们都加入进去，再一次进行同样的查询，用其减去前面查询的结果就得到变化量 ∆，即刚刚加入的这个儿子所统领的树((包括它自己))中能力大于  的牛的数量，即。树状数组可用同样的思路。

#include<algorithm>
#include<cstdio>
#define pl p<<1//左段儿子的编号 
#define pr p<<1|1//右段儿子的编号 
#define Re register int
#define F(a,b) for(i=a;i<=b;++i)
const int N=1e5+3;
int x,i,n,t,Q[N],ip[N],ans[N],nex[N],head[N],tree[N<<2];
struct A{int x,i;bool operator<(A b)const{return x<b.x;};}a[N];
//【重载"<"运算符】自己动手,丰衣足食... 
inline void add(Re x,Re y){Q[++t]=y,nex[t]=head[x],head[x]=t;}//数组维护一个链表 
inline void in(Re &x){//【快读】自己动手,丰衣足食... 
    x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
inline void change(Re p,Re x,Re L,Re R){
//【单点修改】每个人仅有一个能力值，所以是单点修改 
    if(L==R){++tree[p];return;}//单点修改的边界:L==R 
    Re mid=L+R>>1;
    if(x<=mid)change(pl,x,L,mid);//注意:单点修改中，进入递归函数的前提：x<=mid 
    else change(pr,x,mid+1,R);//x>mid
    tree[p]=tree[pl]+tree[pr];//递归完子树后更新 
}
inline int ask(Re p,Re l,Re r,Re L,Re R){//【区间查询】 
    if(l<=L&&R<=r)return tree[p];//区间查询的边界: l<=L&&R<=r
    Re ans=0,mid=L+R>>1;
    if(l<=mid)ans+=ask(pl,l,r,L,mid);//注意区间查询中，进入递归函数的前提：l<=mid 
    if(r>mid)ans+=ask(pr,l,r,mid+1,R);//r>mid 
    return ans;
}
inline void dfs(Re x){//搜索遍历树 
    ans[x]-=ask(1,ip[x]+1,n,1,n);//这里计算出的是其他节点的数据，要减去
    for(Re i=head[x];i;i=nex[i])dfs(Q[i]);//先让儿子更新线段树【单点修改】 
    ans[x]+=ask(1,ip[x]+1,n,1,n);
    //查询大于当前这个点x的等级的一共有多少个【区间查询】，再减去原先的 
    change(1,ip[x],1,n);//让当前这个点x的等级进行【单点修改】 
}
int main(){
    in(n);
    F(1,n)in(a[i].x),a[i].i=i;
    std::sort(a+1,a+n+1);//【离散化】依据每个人的能力p(i)排出他们的等级 
    F(1,n)ip[a[i].i]=i;//用ip[]记录下每个点的等级 
    F(2,n)in(x),add(x,i);//链表建树，实现从根节点到儿子叶节点的遍历 
    dfs(1);//从没有上司的根节点1开始遍历 
    F(1,n)printf("%d\n",ans[i]); 
}

#include<algorithm>
#include<cstdio>
#define Re register int
#define F(a,b) for(i=a;i<=b;++i)
const int N=1e5+3;
int x,i,n,t,C[N],Q[N],ip[N],ans[N],nex[N],head[N];
struct A{int x,i;bool operator<(A b)const{return x<b.x;};}a[N];
inline void add(Re x,Re y){Q[++t]=y,nex[t]=head[x],head[x]=t;}
inline void in(Re &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
inline void addx(Re x){while(x<=n)++C[x],x+=x&(-x);}
inline int ask(Re x){int ans=0;while(x)ans+=C[x],x-=x&(-x);return ans;}
inline void dfs(Re x){
    ans[x]-=ask(n)-ask(ip[x]);
    for(Re i=head[x];i;i=nex[i])dfs(Q[i]);
    ans[x]+=ask(n)-ask(ip[x]);
    addx(ip[x]);
}
int main(){
    in(n);
    F(1,n)in(a[i].x),a[i].i=i;
    std::sort(a+1,a+n+1);
    F(1,n)ip[a[i].i]=i;
    F(2,n)in(x),add(x,i);
    dfs(1);
    F(1,n)printf("%d\n",ans[i]); 
}

 解法二：线段树合并

对于  个点每个点都开一个权值线段树。
对公司上司下属关系形成的树进行遍历，对于每个节点 ，将它所有儿子的权值线段树合并到 ( 用  表示节点 所对应的权值线段树的根节点编号)，然后在  中查询数值大于  的数的个数即为 。

#include<algorithm>
#include<cstdio>
#define pl tr[p].lp//左段儿子的编号 
#define pr tr[p].rp//右段儿子的编号 
#define Re register int
#define F(a,b) for(i=a;i<=b;++i)
const int N=1e5+3;
int x,i,n,t,cnt,Q[N],pt[N],ip[N],ans[N],nex[N],head[N];
struct QAQ{int g,lp,rp,L,R;}tr[N*18];//这里的空间消耗要注意，开太小死活过不了 
struct A{int x,i;bool operator<(A b)const{return x<b.x;};}a[N];
//【重载"<"运算符】自己动手,丰衣足食... 
inline void add(Re x,Re y){Q[++t]=y,nex[t]=head[x],head[x]=t;}//数组维护一个链表 
inline void in(Re &x){//【快读】自己动手,丰衣足食... 
    x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
inline void change(Re p,Re x){//【单点修改】(虽然在这道题中没什么用)
    Re L=tr[p].L,R=tr[p].R;//把编号为p的这个区间所覆盖的范围L,R提出来 
    if(L==R){++tr[p].g;return;}//单修的递归边界:L==R
    Re mid=L+R>>1;
    if(x<=mid)change(pl,x);//注意:单修中进入递归函数的前提：x<=mid 
    else change(pr,x);//x>mid
    tr[p].g=tr[pl].g+tr[pr].g;//递归完子树后更新 
}
inline void creat(Re &p,Re x,Re L,Re R){//建立线段树 
    tr[p=++cnt].L=L,tr[p].R=R;//动态开点，并记录新编号子树所覆盖的区间范围L,R 
    if(L==R){tr[p].g=1;return;}//建立线段树时是一个点一个点的建，所以边界类似于单修 
    Re mid=L+R>>1;
    if(x<=mid)creat(pl,x,L,mid);//递归进入前提也类似于单修 
    else creat(pr,x,mid+1,R);
    tr[p].g=tr[pl].g+tr[pr].g;//递归完子树后更新 
}
inline int merge(Re p,Re q){//【线段树合并】 
    if(!p)return q;if(!q)return p;
    //当需要合并的点的其中一个编号为0时 (即为空)，返回另一个编号 
    tr[p].g+=tr[q].g,p;//把q合并到p上面去 
    pl=merge(pl,tr[q].lp);//分别合并左子树,右子树 
    pr=merge(pr,tr[q].rp);
    return p;
}
inline int ask(Re p,Re l,Re r){//【区间查询】
    if(!p)return 0;
    Re L=tr[p].L,R=tr[p].R;
    if(l<=L&&R<=r)return tr[p].g;//区间查询的边界: l<=L&&R<=r
    Re ans=0,mid=L+R>>1;
    if(l<=mid)ans+=ask(pl,l,r);//注意区间查询中，进入递归函数的前提：l<=mid 
    if(r>mid)ans+=ask(pr,l,r);//r>mid 
    return ans;
}
inline void dfs(Re x){//搜索遍历树 
    for(Re i=head[x];i;i=nex[i]){
        dfs(Q[i]);//先完善儿子的线段树 
        merge(pt[x],pt[Q[i]]);//把儿子合并进来 
    }
    ans[x]=ask(pt[x],ip[x]+1,n);
    //查询大于当前这个点x的等级的一共有多少个【区间查询】，再减去原先的 
}
int main(){
    in(n);
    F(1,n)in(a[i].x),a[i].i=i;
    std::sort(a+1,a+n+1);//【离散化】依据每个人的能力p(i)排出他们的等级 
    F(1,n)ip[a[i].i]=i,creat(pt[a[i].i],i,1,n);
    //用ip[]记录下每个点的等级,并建立线段树
    //【注意】：进入建树时的编号是原本输入时的编号即a[i].i 
    F(2,n)in(x),add(x,i);//链表建搜索树，实现从根节点到儿子叶节点的遍历 
    dfs(1);//从没有上司的根节点1开始遍历 
    F(1,n)printf("%d\n",ans[i]); 
}