BZOJ4756 [Usaco2017 Jan] Promotion Counting

Description

n只奶牛构成了一个树形的公司，每个奶牛有一个能力值pi，1号奶牛为树根。
问对于每个奶牛来说，它的子树中有几个能力值比它大的。

Input

n，表示有几只奶牛 n<=100000
接下来n行为1-n号奶牛的能力值pi
接下来n-1行为2-n号奶牛的经理（树中的父亲）

Output

共n行，每行输出奶牛i的下属中有几个能力值比i大

Sample Input

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

Sample Output

2
0
1
0
0

Solution

如果每个节点都给一个线段树，然后暴力的在父节点将两个线段树合并，那么空间肯定是不够的。因而首先要在空间上进行优化。这里引入了树上的线段树合并。
"树上"还是原来的，DFS的顺序从下往上维护。
"线段树合并"的步骤如下（这里的线段树实际上是一个链）：
对于两颗树的节点u和v
  ①如果u为空，返回v
  ②如果v为空，返回u
  ③否则，新建节点t，整合u和v的信息，然后递归合并u和v的左右子树

inline int merge(int u,int v)
{
    if(!u) return v;
    if(!v) return u;
    int t = ++cnt;
    sum[t]=sum[u]+sum[v];
    les[t]=merge(les[u],les[v]);
    ris[t]=merge(ris[u],ris[v]);
    return t;
}

思考可知，每有一个位置权值同样存在，就要\(O(logn)\)的复杂度。那么合并的复杂度取决于两棵线段树重合部分的大小。
由于权值线段树中被更新的位置通常很均匀分布，所以合并的两棵线段树通常具有很小的相似性。
线段树合并的空间复杂度和时间复杂度都是\(O(nlogn)\)的。
（点大概要开\(2nlogn\)个，测了一下\(n=131072\)‬的时候\(32n\)，\(n=524288\)的时候\(36n\)‬，那么\(2e7\)个应该是肯定够的）

后来看了网上的博客，发现其实这题有更简单的做法。。。
按DFS序把所有点放入并取出一个栈，放入时计算小于\(a_i\)的数量并把\(a_i\)放入线段树中，取出时再计算一次小于\(a_i\)的数量，那么两者之差就是答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+20;
const int maxm = 2e7+20;
int n,id[maxn],a[maxn],b[maxn],fa[maxn],ans[maxn];
int cnt,pid[maxn],sum[maxm],les[maxm],ris[maxm];
vector<int> son[maxn];
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

inline void readin()
{
    n=read();
    for(int i=1;i<=n;++i) a[i]=read(),b[i]=a[i];
    sort(b+1,b+1+n);//题目给定了能力值互异，故不用去重 
    for(int i=1;i<=n;++i) id[i]=lower_bound(b+1,b+1+n,a[i])-b;
    for(int i=2;i<=n;++i) fa[i]=read(),son[fa[i]].push_back(i);
}

inline int query(int qid,int l,int r,int pos)
{
    if(!qid) return 0;
    if(l>pos) return sum[qid];
    int m=(l+r)>>1;
    if(m>pos) return query(ris[qid],m+1,r,pos)+query(les[qid],l,m,pos);
    return query(ris[qid],m+1,r,pos);
}

inline int merge(int u,int v)//the core
{
    if(!u) return v;//某个没有，就直接用另一个，儿子信息可以直接用，不需要更新
    if(!v) return u;
    int t = ++cnt;//都有，就另建一个点记录合并后的信息
    sum[t]=sum[u]+sum[v];
    les[t]=merge(les[u],les[v]);//并且维护新节点的儿子信息
    ris[t]=merge(ris[u],ris[v]);
    return t;
}

inline void modify(int& qid,int l,int r,int pos)//add the current point
{
    if(!qid) qid=++cnt;
    ++sum[qid];
    if(l==r) return;
    int m=(l+r)>>1;
    if(m>=pos) modify(les[qid],l,m,pos);
    else modify(ris[qid],m+1,r,pos);
}

inline int dfs(int now)
{
    for(int i=0;i<son[now].size();++i)
    {
        dfs(son[now][i]);
        pid[now]=merge(pid[now],pid[son[now][i]]);
    }
    ans[now]=query(pid[now],1,n,id[now]);
    modify(pid[now],1,n,id[now]);//add the current point
}

int main()
{
    readin();
    dfs(1);
    for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}