洛谷P3605 线段树合并

题目链接：https://www.luogu.com.cn/problem/P3605
题目大意：给出一颗树，每个点都有一个权值，最后对于每个点，输出在它的子树中，有多少个点的权值比它大。

把权值取负，就是p[j]<p[i]的节点个数。直接线段树合并。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5+5;

int w[N], p[N], lc[N*20], rc[N*20], rt[N*20], tot=0, n;
vector<int> v[N];
int tre[N*20], ans[N];//节点信息

void Insert(int &i, int l, int r, int x){//建树
    if(r<l) return;
    i=++tot;//动态开点
    if(l==r){
        tre[i]++; return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid) Insert(lc[i], l, mid, x);
    if(x>mid) Insert(rc[i], mid+1, r, x);
    tre[i]=tre[lc[i]]+tre[rc[i]];//权值在区间[l, r]的元素个数
}

int Merge(int x, int y){//合并
    if(!x) return y;
    if(!y) return x;
    lc[x]=Merge(lc[x], lc[y]);
    rc[x]=Merge(rc[x], rc[y]);
    tre[x]=tre[lc[x]]+tre[rc[x]];//节点信息合并

    return x;
}

int query(int root, int l, int r, int x){//查询子树中权值<=x的节点个数
    if(!root) return 0;
    if(!x) return 0;
    if(x==r) return tre[root];

    int mid=(l+r)>>1;
    if(x>mid) return tre[lc[root]]+query(rc[root], mid+1, r, x);
    else  return query(lc[root], l, mid, x);
}

void dfs(int u, int fa){
    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to!=fa){
            dfs(to, u);
            rt[u]=Merge(rt[u], rt[to]);//换根合并
        }
    }
    ans[u]=query(rt[u], 1, n, w[u]-1);//查询
}

int main(){

    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &w[i]);
        w[i]=-w[i], p[i]=w[i];
    }
    sort(p+1, p+n+1);
    int cut=unique(p+1, p+n+1)-p-1;
    for(int i=1; i<=n; i++) w[i]=lower_bound(p+1, p+cut+1, w[i])-p;
    for(int i=2; i<=n; i++){
        int x; scanf("%d", &x);
        v[i].push_back(x); v[x].push_back(i);
    }
    for(int i=1; i<=n; i++){
        Insert(rt[i], 1, n, w[i]);//建树
    }
    dfs(1, -1);
    for(int i=1; i<=n; i++){
        printf("%d\n", ans[i]);
    }

    return 0;
}
/* 5 804289384 846930887 681692778 714636916 957747794 1 1 2 3 2 0 1 0 0 */