BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

题意

题目链接

Sol

线段树合并为什么我会在这个时候学这种东西

就是暴力合并两棵线段树(必须动态开节点),遇到空节点就返回

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

对于此题来说,显然子树内与子树外互不影响,因此暴力判断一下翻转之后会不会变优就行了

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 1e7 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, val[MAXN], ls[MAXN], rs[MAXN], tot;
LL ans, c1, c2;
int newtree(int l, int r, int x) {
    val[++tot] = 1;
    if(l == r) return tot;
    int mid = l + r >> 1, now = tot;
    if(x <= mid) ls[now] = newtree(l, mid, x);
    else rs[now] = newtree(mid + 1, r, x);
    return now;
}
int merge(int l, int r, int x, int y) {
    if(!x || !y) return x + y;
    if(l == r) {val[++tot] = val[x] + val[y]; return tot;}
    c1 += 1ll * val[rs[x]] * val[ls[y]], c2 += 1ll * val[ls[x]] * val[rs[y]];
    int mid = l + r >> 1, now = ++tot;
    ls[now] = merge(l, mid, ls[x], ls[y]);
    rs[now] = merge(mid + 1, r, rs[x], rs[y]);
    val[now] = val[x] + val[y];
    return now;
}
int dfs() {
    int v = read();
    if(v) return newtree(1, N, v);
    int now = merge(1, N, dfs(), dfs());
    ans += min(c1, c2); c1 = c2 = 0;
    return now;
}
int main() {
    N = read();
    dfs();
    cout << ans;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

排序算法-希尔排序

上一篇讲解了简单插入排序算法,以及在其基础上优化的二分插入排序算法,但是每次插入需要按间隔为 1 移动有序区的元素,效率不高,下面我们来介绍一种新的插入排序算法...

3484
来自专栏ACM算法日常

字符串的距离(动态规划) - leetcode 72

,因为在刷leetcode的动态规划专题。动态规划虽然定义很简单,但是对于复杂的动态规划题目,很多时候还是很棘手的。

852
来自专栏一直在跳坑然后爬坑

RxJava2操作符之“Scan”作用示例用法运行结果分析总结

扫描,遍历,用法和上一个Reduce操作符差不多,只是这个操作符会将每一个过程的中间产物发射出来,而不是只发射结果

943
来自专栏python读书笔记

《python算法教程》Day9 - 快速排序法快速排序法简介代码展示

这是《python算法教程》第9篇读书笔记,笔记的主要内容为快速排序法。 快速排序法简介 快速排序法运用分治法的方式,将需要排序的序列细分成小序列进行排序。 ...

39310
来自专栏Jed的技术阶梯

图解冒泡排序

在上面实现的代码中,即使n个数本来就是有序的,也会进行(n-1)次排序(只比较,不交换) 优化:当数组已经有序后,就中断循环

1793
来自专栏分布式系统和大数据处理

正则表达式教程

1075
来自专栏desperate633

LintCode 排颜色 II题目分析代码

给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。

982
来自专栏伪君子的梦呓

leetcode 题解~两数之和 ~ C++做法

1775
来自专栏一枝花算不算浪漫

HashMap中的hash算法总结

算法一直是我的弱项,然而面试中基本是必考的项目,刚好上次看到一个HashMap的面试题,今天也来学习下 HashMap中的hash算法是如何实现的。

3042
来自专栏xingoo, 一个梦想做发明家的程序员

快速排序

算法思想:对于输入的子数组a[p:r],按下面三个步骤: 1 分解:以a[p]为基准元素将a[p:r]分成三段,a[p:q-1],a[q],a[q+1:r],使...

2109

扫码关注云+社区

领取腾讯云代金券