Luogu-P3521 “POI2011” ROT-Tree Rotations

Original link: https://blog.chungzh.cn/articles/luogu-p3521/

meaning of the title

Given a binary tree with n leaf nodes . Each leaf node has a weight $p_i$ (note that the root is not a leaf node), and the weights of all leaf nodes constitute a $1 \sim n$ permutation.

For any node of this binary tree, it is guaranteed that it is either a leaf node, or both left and right children exist.

Now you can choose some nodes and swap the left and right subtrees of those nodes.

On the final tree, traverse the entire tree in a preorder traversal and write down the weights of the leaf nodes encountered in order to form a permutation of length n, you need to minimize the inverse logarithm of this permutation.

$2 \leq n \leq 2 \times 10^5$, $0 \leq x \leq n$, the weight of all leaf nodes is a permutation of $1 \sim n$.

analyze

Traverse the entire tree according to the pre-order, and take the leaf nodes. In human speaking, the leaf nodes are taken from left to right.

Important property: After swapping the left and right subtrees of a point, the number of inversion pairs in the left subtree and in the right subtree will not be affected.

Consider an arbitrary node to classify and discuss the reversed pairs of leaves in its subtree:

1. are in the left subtree;
2. are in the right subtree;
3. Spanning left and right subtrees.

After swapping the left and right subtrees, obviously only the third case is affected. The first and second cases can be converted into the third and then recalculated.

How to calculate the answer? At the beginning, for each leaf node, we build a weighted segment tree (dynamic opening point) and record the occurrence of $p_i$ $1$ times. When combining $r1, r2$, the number of pairs in reverse order is $tree[rc[r1]] \times tree[lc[r2]]$. Because the weight interval $[L, R]$ corresponding to $r1, r2$ is the same, and the weight interval corresponding to $lc[r1], lc[r2]$ is $[L, M]$, $rc [r1], rc[r2]$ The corresponding weight interval is $[M+1, R]$, the numbers recorded in $rc[]$ are larger than those in $lc[]$, and $r1$ The number of the corresponding number is less than $r2$ (that is, $r1$ is the left subtree, $r2$ is the right subtree), which satisfies the condition of the reverse order pair.

At this time, the number of reverse order pairs calculated is the case that the left and right subtrees are not exchanged . We only need to calculate the number of reverse order pairs that exchange the left and right subtrees $tree[rc[r2]] \times tree[lc[r1] ]$ to compare, take the smaller value as the answer at the current level.

RECORD

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 

 #include <bits/stdc++.h> using namespace std ; #define LL long long const int MAXN = 200005 ; int n ; LL ans = 0 , u = 0 , v = 0 ; int cnt = 0 , roc = 0 , root [ MAXN << 5 ], lc [ MAXN << 5 ], rc [ MAXN << 5 ], tree [ MAXN << 5 ]; int build ( int l , int r , int p ) { int pos = ++ cnt ; if ( l == r ) { tree [ pos ] = 1 ; return pos ; } int m = ( l + r ) >> 1 ; if ( p <= m ) lc [ pos ] = build ( l , m , p ); else rc [ pos ] = build ( m + 1 , r , p ); tree [ pos ] = tree [ lc [ pos ]] + tree [ rc [ pos ]]; return pos ; } int merge ( int r1 , int r2 , int l , int r ) { if ( ! r1 || ! r2 ) return r1 ^ r2 ; if ( l == r ) { tree [ r1 ] += tree [ r2 ]; return r1 ; } int m = ( l + r ) >> 1 ; u += ( LL ) tree [ rc [ r1 ]] * tree [ lc [ r2 ]]; v += ( LL ) tree [ rc [ r2 ]] * tree [ lc [ r1 ]]; lc [ r1 ] = merge ( lc [ r1 ], lc [ r2 ], l , m ); rc [ r1 ] = merge ( rc [ r1 ], rc [ r2 ], m + 1 , r ); tree [ r1 ] = tree [ lc [ r1 ]] + tree [ rc [ r1 ]]; return r1 ; } int dfs () { int x , pos ; cin >> x ; if ( x == 0 ) { int ls = dfs (), rs = dfs (); u = v = 0 ; pos = merge ( ls , rs , 1 , n ); ans += min ( u , v ); } else { pos = build ( 1 , n , x ); } return pos ; } int main () { cin >> n ; dfs (); cout << ans << endl ; return 0 ; }

This article is reproduced from: https://blog.chungzh.cn/articles/luogu-p3521/
This site is for inclusion only, and the copyright belongs to the original author.