牛客小白月赛11D（分治、RMQ）

ACM算法日常

发布于 2019-05-16 11:39:40

3430

发布于 2019-05-16 11:39:40

文章被收录于专栏：ACM算法日常ACM算法日常

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

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

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

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

输入描述:

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

输出描述：

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

样例：

输入：

输出：

题目解析：

正常地二叉搜索树去做（就是伪代码的做法）会被有序数据卡成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

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-05-12，如有侵权请联系 cloudcommunity@tencent.com 删除

sql

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

sql

登录后参与评论

0 条评论

热度