[BZOJ2212][Poi2011]Tree Rotations

[Poi2011]Tree Rotations

Description

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 . 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< = I < j < = N ) such that(Ai>Aj) in the corona(A1,A2,A3…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的一個排列)。可以任意交換每個非葉子節點的左右孩子。

要求進行一系列交換，使得最終所有葉子節點的權值按照周遊序寫出來，逆序對個數最少。

Input

In the first line of the standard input there is a single integer (2< = N < = 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 ()(1<=P<=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 , 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 , 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).

第一行n

下面每行，一個數x

如果x==0，表示這個節點非葉子節點，遞歸地向下讀入其左孩子和右孩子的資訊，

如果x!=0，表示這個節點是葉子節點，權值為x

1<=n<=200000

Output

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.

一行，最少逆序對個數

Sample Input

3

3

1

2

Sample Output

1

Solution

線段樹的合并

對于一個點x, 我們隻需考慮是否需要交換左右兒子, 遞歸處理左右兒子

Code

#include <bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i++)
#define MS(_) memset(_, 0, sizeof(_))
#define PB push_back
#define MP make_pair
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ckmin(x, y) x = min(x, y)
#define ckmax(x, y) x = max(x, y)
typedef long long ll;
typedef pair<int, int> PII;
typedef vector<int> VI;
template<typename T> inline void read(T &x){
    x = ; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x *  + ch - '0', ch = getchar(); 
}

const int N = ;
struct Node{
    int sum; Node *lc, *rc;
    inline void push_up(){ this->sum = lc->sum + rc->sum; }
}pool[N*], *null=pool, *tail=pool+, *root[N<<];
int n, m, sz;
int l[N<<], r[N<<], v[N<<];
ll ans, cnt1, cnt2;

void get_Tree(int x){
    read(v[x]);
    if (!v[x]){
        l[x] = ++sz; get_Tree(l[x]);
        r[x] = ++sz; get_Tree(r[x]);
    }
}
inline void set_null(){null->lc = null->rc = null;}
inline Node *newNode() {tail->lc = tail->rc = null; return tail++;}
void build(Node *&rt, int tl, int tr, int val){
    if (rt == null) rt = newNode();
    if (tl == tr) { rt->sum = ; return; }
    int mid = tl+tr >> ;
    if (val <= mid) build(rt->lc, tl, mid, val);
    else build(rt->rc, mid+, tr, val);
    rt->push_up();
}
Node *merge(Node *x, Node *y){
    if (x == null) return y;
    if (y == null) return x;
    cnt1 += l * x->rc->sum * y->lc->sum;  
    cnt2 += l * x->lc->sum * y->rc->sum;
    x->lc = merge(x->lc, y->lc);
    x->rc = merge(x->rc, y->rc);
    x->push_up();
    return x;
}
void solve(int x){
    if (!x) return;
    solve(l[x]); solve(r[x]);
    if (!v[x]){
        cnt1 = cnt2 = ;
        root[x] = merge(root[l[x]], root[r[x]]);
        ans += min(cnt1, cnt2);
    }
}
int main(){
    read(n); 
    sz = ; get_Tree();
    set_null(); rep(i, , sz) root[i] = null;

    rep(i, , sz)  if (v[i]) build(root[i], , n, v[i]);
    solve();

    printf("%lld\n", ans);
    return ;
}