一开始做的是这道题 LOJ#2163. 「POI2011」Tree Rotations
时间限制:152 ms 毒瘤卡常qwq
提交记录一翻大多都是 Time Limit Exceeded 分数 60~95 hhh

最后把 make 操作改成非递归的就卡进去了......

相关题目:BZOJ2212: [Poi2011]Tree Rotations

题目描述

This task is a harder version of task Tree Rotations from the second stage of 18th Polish OI. It wasn't used in the contest itself.
本题的一个加强版将限制改为 2n1000000 2 \le n \le 1000000 。测评仍使用原题数据,即 2n200000 2 \leq n \leq 200000

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 1n 1 \ldots 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 , such that in the corona .

rys-crop.gif

The original tree (on the left) with corona 3,1,2 3, 1, 2 has two inversions. A single rotation gives a tree (on the right) with corona 1,3,2 1, 3, 2 , which has only one inversion. Each of these two trees has 5 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.

现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有 nn 个叶子节点,满足这些权值为 1..n1..n 的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换,使得最终所有叶子节点的权值按照中序遍历写出来,逆序对个数最少。

输入格式

In the first line of the standard input there is a single integer n n (2n200000 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 p (1pn 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 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 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 n5000 n \le 5000 .

第一行 nn
下面每行,一个数 xx
如果 xx==0,表示这个节点非叶子节点,递归地向下读入其左孩子和右孩子的信息,
如果 xx!=0,表示这个节点是叶子节点,权值为 xx

输出格式

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.

Solution

交换左右两个子树对以外的结点不会造成影响。所以只要试着交换左右两棵子树,看看答案会不会减小。

可以用线段树合并,每次处理出一棵子树内的权值线段树,然后从下向上合并。

可以用动态开点实现,每次合并的复杂度为 O(log n)O(log~n) 那么时间复杂度为 O(nlog n)O(n log~n)

不妨试试LOJ#2163. 「POI2011」Tree Rotations

POI2011.png

Code

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
56
57
58
59
60
61
#include <cstdio>
#include <cctype>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
const int L=1<<15;
char buf[L],*S,*T;
inline char gc() {
if(S==T) {T=(S=buf)+fread(buf,1,L,stdin); if(S==T) return EOF;}
return *S++;
}
inline int read() {
char c; register int x=0;
for(c=gc();!isdigit(c);c=gc());
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=gc();
return x;
}

struct node {
node *lson,*rson;
int siz;
}m[5000005], *cnt=m, *rt;
int n, c;
long long ans, cnt1, cnt2;

void merge(node *&u,node *&v) {
if(!u) {u=v;return;} if(!v) return;
u->siz += v->siz;
if(u->lson&&v->rson) cnt1 += u->lson->siz *1ll* v->rson->siz;
if(u->rson&&v->lson) cnt2 += u->rson->siz *1ll* v->lson->siz;
merge(u->lson,v->lson);
merge(u->rson,v->rson);
}

void dfs(node *&u) {
c=read();
if(!c) {
node *v;
dfs(u), dfs(v); cnt1=cnt2=0;
merge(u, v);
ans+=cnt1<cnt2?cnt1:cnt2;
}
else {
int l=1, r=n, mid; node *v=cnt+1;
while(1) {
cnt++, cnt->siz++;
if(l==r) break;
mid=(l+r)>>1;
if(c<=mid) cnt->lson=cnt+1, r=mid;
else cnt->rson=cnt+1, l=mid+1;
}
u = v;
}
}

int main() {
n=read();
dfs(rt);
printf("%lld\n", ans);
return ~~(0^_^0);
}