A simple Blog for wyx I've been down the bottle hoping.
3702: 二叉树 线段树
发表于: | 分类: Oi | 评论:0 | 阅读:160

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

这算是线段树合并的经典例题了
在每个节点建立一个权值线段树
然后在合并线段树的时候,分别讨论是否交换区间带来的影响即可
为什么这样是对的?
因为一棵子树对于外面来说已经是固定的了
是否交换对于外面无影响,所以可以递归处理……

时间复杂度?我不会证明,但是Po姐说是$O(nlog(n))$
反正是$O(跑得过)$就是了 = =

 
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 200000+5
#define M 8000000+5
using namespace std;
typedef long long LL;
int ls[M],rs[M],l[M],r[M];
int size[M],v[M],root[M];
 
inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}
 
int n,sz;
int mempool;
 
void build_a_tree(int x)
{
    v[x] = read();
    if(!v[x])
    {
        l[x] = ++sz;
        build_a_tree(l[x]);
        r[x] = ++sz;
        build_a_tree(r[x]);
    }
}
 
void updata(int k)
{
    size[k] = size[ls[k]] + size[rs[k]];
}
 
inline void insert(int &k,int l,int r,int val)
{
    if(!k) k = ++mempool;
    if(l==r){size[k] = 1;return;}
    int mid = (l+r)>>1;
    if(val <= mid)
        insert(ls[k],l,mid,val);
    else insert(rs[k],mid+1,r,val);
    updata(k);  
}
 
LL cnt1 , cnt2;
 
int merge(int x,int y)
{
    if(!x) return y;
    if(!y) return x;
    cnt1 += (LL)size[rs[x]] * size[ls[y]];
    cnt2 += (LL)size[ls[x]] * size[rs[y]];
    ls[x] = merge(ls[x],ls[y]);
    rs[x] = merge(rs[x],rs[y]);
    updata(x);
    return x;
}
 
LL ans = 0;
 
void solve(int x)
{
    if(!x)return;
    solve(l[x]);solve(r[x]);
    if(!v[x])
    {
        cnt1 = cnt2 = 0;
        root[x] = merge(root[l[x]],root[r[x]]);
        ans += min(cnt1,cnt2);
    }
}
 
int main()
{   
    int n = read();
    ++sz;
    build_a_tree(1);
    for(int i=1;i<=sz;++i)
        if(v[i])
            insert(root[i],1,n,v[i]);
    solve(1);
    cout<<ans;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP