Description

给定一棵树，每个点有一个权值，求每个点所有后代中权值比它大的点的个数。

$n\leq10^5$

不怎么难，就是看对数据结构的掌握程度。。

算法一

对每个点维护一个权值线段树，从下往上合并，每次合并该结点所有儿子即可。$O(n\log n)$​​，时间空间常数都很大。

Code

我觉得指针比数组清晰一些，虽然也伴随着一点小风险（访问空指针）。

代码还是很清晰的，不难写。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;

const int maxn = 1e5 + 10;

struct Node
{
    int sum;
    Node *ls, *rs;
    Node() : sum(0), ls(nullptr), rs(nullptr) {}
    void push_up()
    {
        sum = (ls == nullptr ? 0 : ls->sum) + (rs == nullptr ? 0 : rs->sum);
    }
} a[maxn << 5], *root[maxn];
int tot;

Node *modify(int l, int r, int x, Node *p)
{
    if (p == nullptr)
        p = &a[++tot];
    if (l == r)
    {
        (p->sum)++;
        return p;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
        p->ls = modify(l, mid, x, p->ls);
    else
        p->rs = modify(mid + 1, r, x, p->rs);
    p->push_up();
    return p;
}

int query(int l, int r, int x, int y, Node *p)
{
    if (p == nullptr)
        return 0;
    if (l >= x && r <= y)
        return p->sum;
    int mid = (l + r) / 2;
    int res = 0;
    if (x <= mid)
        res += query(l, mid, x, y, p->ls);
    if (y > mid)
        res += query(mid + 1, r, x, y, p->rs);
    return res;
}

Node *merge(int l, int r, Node *a, Node *b)
{
    if (a == nullptr)
        return b;
    if (b == nullptr)
        return a;
    if (l == r)
    {
        a->sum += b->sum;
        return a;
    }
    int mid = (l + r) / 2;
    a->ls = merge(l, mid, a->ls, b->ls), a->rs = merge(mid + 1, r, a->rs, b->rs);
    a->push_up();
    return a;
}

int ans[maxn], val[maxn], b[maxn], n;
std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y); }

void dfs(int x)
{
    for (int v : e[x])
    {
        dfs(v);
        root[x] = merge(1, n, root[x], root[v]);
    }
    ans[x] = query(1, n, val[x] + 1, n, root[x]);
    root[x] = modify(1, n, val[x], root[x]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &val[i]), b[i] = val[i];
    for (int i = 2, x; i <= n; i++)
        scanf("%d", &x), add(x, i);
    std::sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; i++)
        root[i] = &a[++tot], val[i] = std::lower_bound(b + 1, b + 1 + n, val[i]) - b;
    dfs(1);
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
}

算法二

对每个点维护一个平衡树，然后从下向上启发式合并，对每个点查询排名，减一下就是答案。$O(n\log^2n)$​​，虽然复杂度比较高但常数很小，实际上比上面的线段树合并快 $\text{70ms}$​。空间没啥常数。

Code

忽然想起 pb_ds，稍微学了点写了一些。不得不说是真省事，而且红黑树也是真快。（我估计比不少手写 splay/treap 的快）

这代码就更清晰了（）

#include <algorithm>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <set>
using std::cout;
using std::endl;

const int maxn = 2e5 + 10;

inline bool cmp(int x, int y) { return x < y; }

__gnu_pbds::tree<int, __gnu_pbds::null_type, std::less<int>,
                 __gnu_pbds::rb_tree_tag,
                 __gnu_pbds::tree_order_statistics_node_update>
    S[maxn], *root[maxn];

std::vector<int> e[maxn];
inline void add(int x, int y) { e[x].push_back(y); }

int n, a[maxn], ans[maxn];

void dfs(int x)
{
    auto mx = root[x];
    for (int v : e[x])
    {
        dfs(v);
        if (root[v]->size() > mx->size())
            mx = root[v];
    }
    root[x] = mx;
    for (int v : e[x])
    {
        if (root[v] != root[x])
        {
            for (int it : *root[v])
                root[x]->insert(it);
            root[v]->clear();
        }
    }
    ans[x] = root[x]->size() - root[x]->order_of_key(a[x]);
    root[x]->insert(a[x]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), root[i] = &S[i];
    for (int i = 2, x; i <= n; i++)
        scanf("%d", &x), add(x, i);
    dfs(1);
    for (int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
}

算法三

搞个 dfs 序出来，然后就变成序列题目，可以用类似逆序对的方法做，树状数组常数很小。

或者分块，我还看到有主席树的qwq。