博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj2212 [POI2011]Tree Rotations
阅读量:5875 次
发布时间:2019-06-19

本文共 1489 字,大约阅读时间需要 4 分钟。

分析

首先我们不难发现交换两棵子树,它们自身的逆序对个数是不变的,改变的只是由一棵子树的x和另一棵子树的y组成的二元组(x,y),所以我们可以考虑使用线段树合并。我们对于每一个叶子节点建一棵权值线段树,然后将他们一一合并,而对于每一个节点是否旋转左右儿子只需要比较这两种情况产生的逆序对个数即可。详见代码。

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;long long a[4000100],cnt,son[2][4000100],root,ans,res;long long CNT,SON[2][4000100],n,rt[4000100],sum[4000100];inline void addnode(long long &x,long long le,long long ri,long long pl){ x=++cnt; sum[x]++; if(le==ri)return; long long mid=(le+ri)>>1; if(mid>=pl)addnode(son[0][x],le,mid,pl); else addnode(son[1][x],mid+1,ri,pl); return;}inline void build(long long &x){ x=++CNT; scanf("%lld",&a[x]); if(a[x]){ addnode(rt[x],1,n,a[x]); return; } build(SON[0][x]); build(SON[1][x]); return;}inline long long mer(long long x,long long y){ if(!x)return y; if(!y)return x; res+=sum[son[0][x]]*sum[son[1][y]]; son[0][x]=mer(son[0][x],son[0][y]); son[1][x]=mer(son[1][x],son[1][y]); sum[x]=sum[son[0][x]]+sum[son[1][x]]; return x;}inline void dfs(long long x){ long long le=SON[0][x],ri=SON[1][x]; if(a[x])return; dfs(le),dfs(ri); long long tot=sum[rt[le]]*sum[rt[ri]]; res=0; rt[x]=mer(rt[le],rt[ri]); ans+=min(res,tot-res); return;} int main(){ scanf("%lld",&n); build(root); dfs(root); printf("%lld\n",ans); return 0;}

转载于:https://www.cnblogs.com/yzxverygood/p/9498312.html

你可能感兴趣的文章
ASP.NET画直方图
查看>>
我的友情链接
查看>>
jquery 实现下拉菜单
查看>>
grep找出不包含指定字符的文件名
查看>>
实现底部导航栏及切换tab重新加载的问题解决
查看>>
[推荐]如何保护Web站点免受跨站点脚本***?
查看>>
CentOS 6.2 编译Apache使其支持HTTPS
查看>>
用cronolog分割tomcat的catalina.out文件
查看>>
linux命令练习:磁盘管理相关练习
查看>>
Git 拉取服务器的代码更新后提交
查看>>
OC 重写构造方法instancetype
查看>>
iOS -无网络页面的创建、判断当前网络是否正常、创建有无网络判断的UIViewController根视图...
查看>>
onInterceptTouchEvent事件和onTouchEvent事件
查看>>
配置管理小报111217:Eclipse和myEclipse介绍
查看>>
js window.event对象详尽解析
查看>>
备份Intellij IDEA配置的两种方式
查看>>
Swift - 时间戳简单处理
查看>>
浏览器的缓存策略详解
查看>>
配置android开发环境eclipse获取ADT获取不到
查看>>
android获取string.xml的值
查看>>