专栏首页ACM算法日常牛客小白月赛11D(分治、RMQ)

牛客小白月赛11D(分治、RMQ)

补充:建树过程中会更新lc和rc,这实质上是一个二叉查找树的插入过程。

定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

问题:每次 Insert 操作结束之后,输出当前节点的深度和。

这里我们定义 R 节点的深度为 0。

输入描述:

第一行一个整数N(<=3e5),表示操作次数。接下来N行,第i行有一个值val_i,表示第i次操作的val。

输出描述:

N行,每行输出该次操作完后的答案。

样例:

输入:

8

3

5

1

6

8

7

2

4

输出:

0

1

2

4

7

11

13

15

题目解析:

正常地二叉搜索树去做(就是伪代码的做法)会被有序数据卡成n方。

离线做法。考虑记录id(即第几个出现)后的数字排序,可以像中序遍历一样,先找到[l, r]中最早出现的那个,它的ans就是当前深度,然后两边进行分治解决。但如果暴力扫一遍去寻找最早出现的,还是n方的,所以用ST表预处理一下区间最小值。

代码257ms:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 5;
int N;
long long Ans[maxn];
struct V {
    int val, id;
    bool operator < (const V &rhs) const {
        return val < rhs.val;
    }
}a[maxn];
int ST[maxn][20], pos[maxn];

void Pre() {
    for (int i = 1; i <= N; i++)
        ST[i][0] = a[i].id;
    for (int j = 1; (1 << j) <= N; j++) {
        for (int i = 1; i + (1 << j) - 1 <= N; i++) {
            ST[i][j] = min(ST[i][j - 1], ST[i + (1 << (j-1))][j - 1]);
        }
    }
    for (int i = 1; i <= N; i++)
        pos[a[i].id] = i;
}

int Query(int l, int r) {
    int j = log2(r - l + 1);
    return min(ST[l][j], ST[r - (1 << j) + 1][j]);
}

void Divide(int l, int r, int depth) {
    if (l > r)    return;

    int id = Query(l, r);
    Ans[id] = depth;
    Divide(l, pos[id] - 1, depth + 1);
    Divide(pos[id] + 1, r, depth + 1);
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &a[i].val);
        a[i].id = i;
    }
    sort(a + 1, a + 1 + N);
    Pre();
    Divide(1, N, 0);
    for (int i = 1; i <= N; ++i) {
        Ans[i] += Ans[i - 1];
        printf("%lld\n", Ans[i]);
    }
    return 0;
}

最后,这套题的其他题目和解析地址:https://www.cnblogs.com/AlphaWA/p/10651045.html

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:AlphaWA

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-12

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU6370:Werewolf 推理+拓扑排序 2018第六场杭电多校

    "The Werewolves" is a popular card game among young people.In the basic game, th...

    ACM算法日常
  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • 【USACO 3.2】Magic Squares

    4*2个格子分别为 1234 8765 的魔板有3种操作,A:上下两排互换,B:最后一列放到第一列前面,C:中间四个顺时针旋转1格。 现在给出目标状态,...

    饶文津
  • 弱校联盟10.3

    n对括号最多需要1+2+..+n次交换,当它是)))..(((的形式时,)))(((需要6次,然后把中间两个交换一下,))()((就还需要5次,再交换一次靠近左...

    饶文津
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • 1365 浴火银河星际跳跃

    1365 浴火银河星际跳跃 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 小...

    attack
  • 【计算机本科补全计划】CCF计算机职业资格认证 2016-09 试题详解

    正文之前 我要东山再起了!!没错CCF迫在眉睫(其实是我以为报名之后一个月才考,结果报名截止之后一周就考试!(╯‵□′)╯︵┻━┻!!!还能好好做朋友吗!!)所...

    用户1687088
  • 每天一算: Number of Boomerangs

    五分钟学算法
  • 颜色聚合向量

    package com.imageretrieval.features; /** * 颜色聚合向量<br> * 参考链接:http://www.docin...

    Venyo

扫码关注云+社区

领取腾讯云代金券