题解 P3605 【[USACO17JAN]Promotion Counting晋升者计数】

sjkmost · 2017-12-03 03:42:14 · 题解

题意就是给出一个点权不相同的树然后问你每个结点子树中权值大于它的节点个数。

我们可以先搞出一个DFS序来，然后就是静态区间rank查询了。

对于静态区间rank查询，我们可以先把所有的询问（结点）按权值排序，然后依次加入树状数组里面，每次加入之前查询[l,r]的区间和。

时间复杂度O(nlogn)。

const int MAXN = 100000 + 5;

int hed[MAXN], nxt[MAXN << 1], tot[MAXN << 1], val[MAXN], fa[MAXN], L[MAXN], R[MAXN], bit[MAXN], ask[MAXN];
pair < int, int > point[MAXN];

inline void AddEdge(int x, int y) { //加边 
    static int cnt;
    ++ cnt;
    tot[cnt] = y;
    nxt[cnt] = hed[x];
    hed[x] = cnt;
}

void DFS(int u) {
    static int cnt;
    ++ cnt;
    L[u] = cnt;  //更新结点u在DFS序中的映射 
    point[cnt] = make_pair(val[u], u);  //权值与结点编号，方便排序后查找DFS序 
    int v;
    for (int k = hed[u]; k; k = nxt[k]) {  //DFS 
        v = tot[k];
        if (v != fa[u])
            DFS(v);
    }
    R[u] = cnt;  //DFS结束后的计数器值就是结点u子树在DFS序中的范围 
}

int n;

#define lowbit(x) (x) & -(x) 
inline void Modify(int i) {  //树状数组操作 
    for (; i <= n; i += lowbit(i))
        ++ bit[i]; 
}

inline int Query(int i) {
    int k = 0;
    for (; i; i -= lowbit(i))
        k += bit[i];
    return k;
}

inline bool Comp(const pair < int, int > &a, const pair < int, int > &b) {  //按权值从大到小排序 
    return a.first > b.first;
}

int main() {
    get, n;
    For(i, 1, n)
        get, val[i];
    int dx;
    For(i, 2, n) {
        get, dx;
        fa[i] = dx;
        AddEdge(dx, i);
        AddEdge(i, dx);
    }
    DFS(1);  //先DFS一遍找出DFS序 
    sort(point + 1, point + n + 1, Comp);  //排序 
    For(i, 1, n) {
        ask[point[i].second] = Query(R[point[i].second]) - Query(L[point[i].second] - 1);  //在当前结点之前插入树状数组的一定是比当前结点权值大的，直接查找即可 
        Modify(L[point[i].second]);
    }
    For(i, 1, n)
        put, ask[i], '\n';
    return 0;
}