Cancel

1851 - Minimum Level to Include

Other

·

June 11, 2023

题干

问题描述

源代码

破题

一般性思路

看起来像是区间上的查询问题，而分段树总是可以解决这样的问题。

用区间的长度表示一个区间的值，重叠部分取最小值，离散化区间坐标后建树，这些都是容易的，但问题是，对每次查询的值又要对它使用哪个或哪些离散化的坐标的查询结果进行表示？

不可能的在线查询

一开始我的考虑是如果对查询的值在区间坐标上做二分查找，如果成功的话就用那个找到的坐标在树上查询，如果失败的话就比较左右两个临近坐标的是区间的结束还是开始，但是这样也无法正确解决问题，因为左右两个坐标是区间取得到的，它的结果可能是多个区间重叠得到的，而在查询值的位置其中决定最小值的区间可能已经结束了，此时查询值就取到了错误的值。

只能把区间值和查询值一并离散化，然后直接查询，详见解①。

离线思路

在实现完分段树版本后就在考虑，有没有树状数组的实现？ 按照一般思路这是难以想象的，但是这个过程中意识到既然所有的查询都是提前已知的，那么完全可以做离线查询，如果把查询值进行排序，按照顺序进行扫描，这不就完全回到了天际线问题 ?！ 而这个思路也就是扫描线的思路。

对应有树状数组的解② 和 优先级队列的解③

解①：

use std::{
    cmp::{max, min},
    collections::HashMap,
};

pub fn solve(intervals: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
    let mut data: Vec<i32> = intervals
        .iter()
        .cloned()
        .flatten()
        .chain(queries.iter().cloned())
        .collect();

    data.sort_unstable();
    data.dedup();

    let data_map: HashMap<i32, usize> = data
        .iter()
        .cloned()
        .enumerate()
        .map(|(i, x)| (x, i))
        .collect();

    let mut tree = SegmentTree::new(data_map.len());

    for interval in intervals {
        let l = interval[0];
        let r = interval[1];

        let val = r - l + 1;
        let l = *data_map.get(&l).unwrap();
        let r = *data_map.get(&r).unwrap();

        tree.update(l, r, val);
    }

    let mut ans = Vec::with_capacity(queries.len());

    for q in queries {
        let i = data.binary_search(&q).unwrap();

        let res = tree.query(i, i);

        if res == 0 {
            ans.push(-1);
        } else {
            ans.push(res);
        }
    }

    ans
}

macro_rules! combine {
    ($inplace: expr, $val:expr) => {
        if $val > 0 && (*$inplace == 0 || $val < *$inplace) {
            *$inplace = $val;
        }
    };
}

/// DFS 型
struct SegmentTree {
    /// range update
    data: Vec<i32>,
    range_end: usize,
}

impl SegmentTree {
    fn new(range_end: usize) -> Self {
        Self {
            data: vec![0; range_end * 2],
            range_end,
        }
    }

    fn update(&mut self, l: usize, r: usize, val: i32) {
        self.update_(l, r, 0, self.range_end - 1, 0, val)
    }

    fn update_(&mut self, l: usize, r: usize, tl: usize, tr: usize, i: usize, val: i32) {
        if l > r {
            return;
        }

        if l == tl && r == tr {
            combine!(&mut self.data[i], val);
        } else {
            let mid = (tl + tr) / 2;
            let sub_len = mid - tl + 1;

            let i_lf = i + 1;
            let i_rh = i + 2 * sub_len;

            combine!(&mut self.data[i_lf], self.data[i]);
            combine!(&mut self.data[i_rh], self.data[i]);

            self.update_(l, min(mid, r), tl, mid, i_lf, val);
            self.update_(max(l, mid + 1), r, mid + 1, tr, i_rh, val);
        }
    }

    fn query(&mut self, l: usize, r: usize) -> i32 {
        self.query_(l, r, 0, self.range_end - 1, 0)
    }

    fn query_(&mut self, l: usize, r: usize, tl: usize, tr: usize, i: usize) -> i32 {
        if l > r {
            return 0;
        }

        if l == tl && r == tr {
            self.data[i]
        } else {
            let mid = (tl + tr) / 2;
            let sub_len = mid - tl + 1;

            let i_lf = i + 1;
            let i_rh = i + 2 * sub_len;

            combine!(&mut self.data[i_lf], self.data[i]);
            combine!(&mut self.data[i_rh], self.data[i]);

            let lv = self.query_(l, min(mid, r), tl, mid, i_lf);
            let rv = self.query_(max(l, mid + 1), r, mid + 1, tr, i_rh);

            if lv == 0 {
                rv
            } else if rv == 0 {
                lv
            } else {
                min(lv, rv)
            }
        }
    }
}

这道题的输入数据和查询数据都有相当的规模，区间数量有 $10^5$ ，查询数量有 $10^7$，这对性能还是有一定要求的，

运行时间： $250$ ms

解②：

use std::collections::HashMap;

pub fn solve(mut intervals: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
    intervals.sort_unstable();

    let mut queries: Vec<(i32, usize)> = queries
        .into_iter()
        .enumerate()
        .map(|(i, x)| (x, i))
        .collect();

    queries.sort_unstable();

    let mut data: Vec<i32> = queries
        .iter()
        .map(|x| x.0)
        .chain(intervals.iter().map(|v| v[1]))
        .collect();

    data.sort_unstable();
    data.dedup();

    let data_map: HashMap<i32, usize> = data
        .iter()
        .cloned()
        .enumerate()
        .map(|(i, x)| (x, i))
        .collect();

    let mut bit = FakeBIT::new(data_map.len());

    let mut ans = vec![0; queries.len()];

    let mut prev_q_raw = 0;
    let mut prev_ans = 0;
    let mut i = 0;

    for (q_raw, q_idx) in queries {
        if prev_q_raw == q_raw {
            ans[q_idx] = prev_ans;

            continue;
        }

        let q = *data_map.get(&q_raw).unwrap();

        while i < intervals.len() {
            let l = intervals[i][0];
            let r = intervals[i][1];

            if l > q_raw {
                break;
            }

            i += 1;

            if r < q_raw {
                continue;
            }

            bit.add(*data_map.get(&r).unwrap(), q, r - l + 1);
        }

        let suffix = bit.suffix(q);
        let res = if suffix > 0 { suffix } else { -1 };

        ans[q_idx] = res;

        prev_q_raw = q_raw;
        prev_ans = res;
    }

    ans
}

macro_rules! combine {
    ($inplace: expr, $val:expr) => {
        if $val > 0 && (*$inplace == 0 || $val < *$inplace) {
            *$inplace = $val;
        }
    };
}

macro_rules! range {
    ($i:ident) => {
        ((($i + 1) as isize) & -(($i + 1) as isize)) as usize
    };
}

struct FakeBIT {
    data: Vec<i32>,
}

impl FakeBIT {
    fn new(range_end: usize) -> Self {
        Self {
            data: vec![0; range_end],
        }
    }

    fn add(&mut self, mut i: usize, end: usize, addend: i32) {
        loop {
            combine!(&mut self.data[i], addend);

            if i < range!(i) || i < end {
                break;
            }

            i -= range!(i);
        }
    }

    /// query i
    fn suffix(&self, mut i: usize) -> i32 {
        let mut acc = 0;

        while i < self.data.len() {
            combine!(&mut acc, self.data[i]);

            i += range!(i);
        }

        acc
    }
}

本实现对树状数组的活用的具体解释在天际线问题的相关章节里。

运行时间：$115$ ms

解③：

use std::{collections::BinaryHeap, cmp::Reverse};


pub fn solve(mut intervals: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
    intervals.sort_unstable_by_key(|v| v[0]);

    let mut queries: Vec<(i32, usize)> = queries
        .into_iter()
        .enumerate()
        .map(|(i, x)| (x, i))
        .collect();

    queries.sort_unstable();

    let mut ans = vec![0; queries.len()];

    let mut prev_q_raw = 0;
    let mut prev_ans = 0;

    let mut i = 0;
    let mut heap = BinaryHeap::new();

    for (q_raw, q_idx) in queries {
        if prev_q_raw == q_raw {
            ans[q_idx] = prev_ans;

            continue;
        }

        while i < intervals.len() {
            let l = intervals[i][0];
            let r = intervals[i][1];

            if l > q_raw {
                break;
            }

            i += 1;

            if r < q_raw {
                continue;
            }

            heap.push(PQE(r, Reverse(r - l + 1)));
        }

        let mut res = -1;

        while let Some(PQE(r, v)) = heap.peek() {
            if *r >= q_raw {
                res = v.0;
                break;
            }

            heap.pop();
        }

        ans[q_idx] = res;

        prev_q_raw = q_raw;
        prev_ans = res;
    }

    ans
}


#[derive(PartialEq, Eq, Ord)]
struct PQE(i32, Reverse<i32>);

impl PartialOrd for PQE {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.1.partial_cmp(&other.1)
    }
}

运行时间：$60$ ms ，beats 100%

注解

© minghu6

·

theme

Simplex theme logo

by golas