bzoj3702二叉树线段树合并

2022-10-30 23:02:19

3702: 二叉树

Time Limit: 15 Sec Memory Limit: 256 MB
Submit: 600 Solved: 272
[Submit][Status][Discuss]

Description

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

Input

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

Output

一行，最少逆序对个数。

Sample Input

3
0
0
3
1
2

Sample Output

HINT

对于100%的数据：2<=n<=200000。

两棵子树交换不影响子树内的值,所以每次只考虑相邻两棵子树怎样放,再考虑上一层怎么放

线段树合并: 开权值线段记录原树中每个节点的子树对应拥有的值,向上合并的时候统计答案

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ll long long

#define N 200050

using namespace std;

int n,tot,cnt,v[N*3],rt[N*3],l[N*3],r[N*3],ls[N*20],rs[N*20],sum[N*20];

ll ans,a,b;

void tree(int &x){

    x=++tot;

    scanf("%d",&v[tot]);

    if(v[tot])return;

    tree(l[x]);

    tree(r[x]);

}

void update(int &u,int l,int r,int p){

    if(!u)u=++cnt;sum[u]++;

    if(l==r)return;

    int mid=l+r>>1;

    if(p<=mid)update(ls[u],l,mid,p);

    else update(rs[u],mid+1,r,p);

}

int merge(int x,int y){

    if(!x)return y;

    if(!y)return x;

    a+=1ll*sum[ls[x]]*sum[rs[y]];

    b+=1ll*sum[rs[x]]*sum[ls[y]];

    ls[x]=merge(ls[x],ls[y]);

    rs[x]=merge(rs[x],rs[y]);

    sum[x]=sum[ls[x]]+sum[rs[x]];

    return x;

}

void solve(int x){

    if(!x)return;

    solve(l[x]);solve(r[x]);

    if(v[x])return;

    a=0;b=0;

    rt[x]=merge(rt[l[x]],rt[r[x]]);

    ans+=min(a,b);

}

int main(){

    scanf("%d",&n);

    int root;tree(root);

    for(int i=1;i<=tot;i++)

    if(v[i])update(rt[i],1,n,v[i]);

    solve(1);cout<<ans;

    return 0;

}

码农公寓