Rockdu's Blog

题目描述

Byteasar the gardener is growing a rare tree called Rotatus Informatikus.

It has some interesting features:

The tree consists of straight branches, bifurcations and leaves.

The trunk stemming from the ground is also a branch.

Each branch ends with either a bifurcation or a leaf on its top end.

Exactly two branches fork out from a bifurcation at the end of a branch - the left branch and the right branch.

Each leaf of the tree is labelled with an integer from the range $1..n$ .

The labels of leaves are unique.

With some gardening work, a so called rotation can be performed on any bifurcation, swapping the left and right branches that fork out of it.

The corona of the tree is the sequence of integers obtained by reading the leaves' labels from left to right.

Byteasar is from the old town of Byteburg and, like all true Byteburgers, praises neatness and order.

He wonders how neat can his tree become thanks to appropriate rotations.

The neatness of a tree is measured by the number of inversions in its corona, i.e. the number of pairs $(i,j)$ , $1\le i<j\le n$ such that a_i>a_jai​>aj​ in the corona a_1,a_2,\cdots,a_na1​,a2​,⋯,an​ .

The original tree (on the left) with corona $3,1,2$ has two inversions.

A single rotation gives a tree (on the right) with corona $1,3,2$ , which has only one inversion.

Each of these two trees has 5 branches.

Write a program that determines the minimum number of inversions in the corona of Byteasar's tree that can be obtained by rotations.

给一棵n(1≤n≤200000个叶子的二叉树，可以交换每个点的左右子树，要求前序遍历叶子的逆序对最少。

输入输出格式

输入格式：

In the first line of the standard input there is a single integer $n$ ( $2\le n\le 200000$ ) that denotes the number of leaves in Byteasar's tree.

Next, the description of the tree follows.

The tree is defined recursively:

• if there is a leaf labelled with $p$ ( $1\le p\le n$ ) at the end of the trunk (i.e., the branch from which the tree stems),then the tree's description consists of a single line containing a single integer $p$

• if there is a bifurcation at the end of the trunk, then the tree's description consists of three parts:

• • the first line holds a single number $0$
• • then the description of the left subtree follows (as if the left branch forking out of the bifurcation was its trunk),
• • and finally the description of the right subtree follows (as if the right branch forking out of the bifurcation was its trunk).

In tests worth at least 30% of the points it additionally holds that $n\le 5000$ .

输出格式：

In the first and only line of the standard output a single integer is to be printed:

the minimum number of inversions in the corona of the input tree that can be obtained by a sequence of rotations.

输入输出样例

3
0
0
3
1
2

1

说明

给一棵n(1≤n≤200000个叶子的二叉树，可以交换每个点的左右子树，要求前序遍历叶子的逆序对最少。

 考虑对于一个子树根，因为左右子树内外的操作不影响，我们只要对每一个节点贪心选择交换即可。那么问题就转换为对每一个节点求出左右子树交换、不交换对于答案的贡献。也就是对于左子树的每一个元素，求出右子树比它大的元素个数，维护两个序列拼接的可以线段树合并做：每一次合并到端点对答案的贡献就是左子树大小乘右子树大小。

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int maxn = 4e5 + 5;
int n, m, w[maxn], tree[maxn][2], rt, cnt;

namespace SGT {
    struct node {
        int size, ch[2];
    }tree[maxn * 30];
    int root[maxn], rtcnt, cnt;
    void push_up(int rt) {
        tree[rt].size = tree[tree[rt].ch[0]].size + tree[tree[rt].ch[1]].size;
    }
    void insert(int p, int tl, int tr, int & rt) {
        if(!rt) rt = ++cnt;
        if(tl == tr) {++tree[rt].size;return;}
        int mid = tl + tr >> 1;
        if(p <= mid) insert(p, tl, mid, tree[rt].ch[0]);
        else insert(p, mid + 1, tr, tree[rt].ch[1]);
        push_up(rt);
    }
    int merge(int x, int y, int & ord, int & inv) {
        int ret = 0;
        if(!x || !y) return x + y;
        tree[x].size += tree[y].size;
        ord += tree[tree[x].ch[0]].size * tree[tree[y].ch[1]].size;
        inv += tree[tree[y].ch[0]].size * tree[tree[x].ch[1]].size;
        tree[x].ch[0] = merge(tree[x].ch[0], tree[y].ch[0], ord, inv);
        tree[x].ch[1] = merge(tree[x].ch[1], tree[y].ch[1], ord, inv);
        return push_up(x), x;
    }
}

void Read(int & rt) {
    rt = ++cnt;
    scanf("%lld", &w[rt]);
    if(w[rt]) {SGT::insert(w[rt], 1, n, SGT::root[rt]); return;}
    Read(tree[rt][0]);
    Read(tree[rt][1]);
}

int solve(int u, int & rt) {
    int ans = 0, x, y, ord = 0, inv = 0;
    if(w[u]) return rt = SGT::root[u], 0;
    ans += solve(tree[u][0], x);
    ans += solve(tree[u][1], y);
    rt = SGT::merge(x, y, ord, inv);
    ans += min(ord, inv);
    return ans;
}
int lstroot;
signed main() {
    scanf("%lld", &n);
    Read(rt);
    printf("%lld", solve(1, lstroot));
    return 0;
}