首页 > 其他分享 >P3521 [POI2011] ROT-Tree Rotations

P3521 [POI2011] ROT-Tree Rotations

时间:2024-04-02 22:00:43浏览次数:25  
标签:p2 p1 rs int sum POI2011 Tree ls ROT

P3521 [POI2011] ROT-Tree Rotations

线段树合并

首先左右子树交换只会改变「跨过左右子树的逆序对」数量,对其他逆序对不会有任何影响,所以我们选择对每个结点的左右子树求解,判断是否交换。

考虑对于每个节点建一个权值线段树,那么贡献就可以在 merge 操作中求解,原因是在权值线段树上二分,可以计算跨过 \(mid\) 的逆序对,然后继续递归求解,这部分类似归并排序。

知道了交换与不交换的贡献,加最小值即可。

复杂度 \(O(n\log n)\)。

merge 操作中计算贡献是很重要的做法,要熟练。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

typedef long long i64;
const int N = 2e5 + 10;
i64 tot, ret1, ret2;
struct seg {
	int ls, rs;
	i64 sum;
} t[N * 40];
i64 n, ans;
void pushup(int u, int ls, int rs) {t[u].sum = t[ls].sum + t[rs].sum;}
int ins(int &u, int l, int r, int x) {
	if(!u) u = ++tot;
	if(l == r) {
		t[u].sum++;
		return u;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) ins(t[u].ls, l, mid, x);
	else ins(t[u].rs, mid + 1, r, x);
	pushup(u, t[u].ls, t[u].rs);
	return u;
}
int mg(int p1, int p2, int l, int r) {
	if(l == r) {
		t[p1].sum += t[p2].sum;
		return p1;
	}
	int mid = (l + r) >> 1;
	ret1 += t[t[p1].rs].sum * t[t[p2].ls].sum;
	ret2 += t[t[p2].rs].sum * t[t[p1].ls].sum;
	if(t[p1].ls && t[p2].ls) mg(t[p1].ls, t[p2].ls, l, mid);
	else if(t[p2].ls) t[p1].ls = t[p2].ls;
	if(t[p1].rs && t[p2].rs) mg(t[p1].rs, t[p2].rs, mid + 1, r);
	else if(t[p2].rs) t[p1].rs = t[p2].rs;
	pushup(p1, t[p1].ls, t[p1].rs);
	return p1;
}
int dfs() {
	int x, rt;
	std::cin >> x;
	if(x == 0) {
		int ls = dfs(); 
		int rs = dfs();
		ret1 = ret2 = 0;
		rt = mg(ls, rs, 1, n);
		ans += std::min(ret1, ret2);
	} else {
		rt = ++tot;
		ins(rt, 1, n, x);
	}
	return rt; 
}
void Solve() {
	std::cin >> n;

	dfs();
	std::cout << ans << "\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	Solve();

	return 0;
}

标签:p2,p1,rs,int,sum,POI2011,Tree,ls,ROT
From: https://www.cnblogs.com/FireRaku/p/18111600

相关文章

  • CF490F Treeland Tour
    CF490FTreelandTour线段树合并考虑维护\(lis_{u,i}/lds_{u,i}\)当前子树\(u\)中以\(i\)结尾的上升子序列/下降子序列。考虑转移,实质上就是合并每个儿子的信息,用线段树合并即可。考虑如何统计答案,当枚举到儿子\(v\)时,维护答案分两种情况:选\(u\)点,那么就是前面的\(......
  • 1946C - Tree Cutting
    CF难度:1600从题意中看是一道比较经典的树形DP问题,题目要求的是把一棵树切k次,求被分割的树中最小的节点x的最大值是多少,因此可以采用二分写法,对于每一个树中,满足mid的节点个数是否等于k个。题目链接:TreeCutting对于每个二分,都用一遍dfs遍历树,因此check函数可以这么写:boolc......
  • IP(Internet Protocol)是一种网络协议,用于在网络中发送和接收数据包
    IP(InternetProtocol)是一种网络协议,用于在网络中发送和接收数据包。它是一个无连接的、不可靠的数据报协议,负责将数据从源主机传输到目标主机。IP协议的主要功能包括寻址、路由和分段。寻址:IP协议为每个连接到网络的设备分配一个唯一的IP地址,这个地址用于在网络中识别设备......
  • WPF实现树形表格控件(TreeListView)
    前言本文将探讨如何利用WPF框架实现树形表格控件,该控件不仅能够有效地展示复杂的层级数据,还能够提供丰富的个性化定制选项。我们将介绍如何使用WPF提供的控件、模板、布局、数据绑定等技术来构建这样一个树形表格。一、运行效果1.1默认样式1.2自定义样式二、代码实现......
  • 详解 Protobuf 以及在 Go 中如何使用 gRPC
    什么是RPC?RPC指的是远程过程调用(RemoteProcedureCall),简单理解就是一个节点请求另一个节点提供的服务。假设有两台服务器A和B,一个部署在A服务器上的应用,想要调用B服务器上某个应用提供的函数/方法。但由于不在同一个内存空间,所以不能直接调用,而是需要通过网络来表达......
  • 前端自动部署报错“http://registry.npm.taobao.org/****/download/array-tree-filter
    自动部署时报错我试过更改淘宝镜像为https://registry.npmmirror.com但都不生效报错如下图:代码中的配置文件如下如上配置在其他测试环境均正常,只在生产环境报错求大佬帮忙看看是什么原因呀......
  • 加密软件VMProtect教程:使用脚本-功能
    VMProtect是新一代软件保护实用程序。VMProtect支持德尔菲、BorlandCBuilder、VisualC/C++、VisualBasic(本机)、VirtualPascal和XCode编译器。同时,VMProtect有一个内置的反汇编程序,可以与Windows和MacOSX可执行文件一起使用,并且还可以链接编译器创建的MAP文件,以快速选择......
  • 从 String.prototype.substring 的区间开始
    因为使用String.prototype.substring(start,end)或者Array.prototype.slice(start,end)的时候偶尔会想不起来这些函数的区间代表的是什么。在这里记录一下。不同函数的差异这些区间都是[start,end),即是包括start,但是不包括end(当没有传入end时,end视为数组或者字符串......
  • CF1935F Andrey's Tree (树上乱搞)
    题意:有一颗n个节点的数,需要解决以下问题:先去掉节点v和与其相连的边;然后在剩余的图上加若干条边,在(x,y)之间连边的代价是∣x−y∣。求使得图连通的最小代价。计算删除顶点v后,每个顶点1≤v≤n至少需要花费多少金币才能使图形重新成为一棵树,以及需要添加哪些边。做法:首先可......
  • [hdu6647]Bracket Sequences on Tree 解题报告
    oj:https://gxyzoj.com/d/hzoj/p/3575因为自己的脑残原因,调了8个小时啊!!!切入正题Part1假定1为根,可以发现,如果u的两棵子树同构,则他们遍历的顺序不影响答案所以,就可以将子树按哈希值分类,这道题就变成了一个可重复组合问题,设\(f_i\)表示以1为根时i的方案数,\(a_i\)表示某一种哈......