Codeforces Round #773 (Div. 1) C. Anonymity Is Important

問題

https://codeforces.com/contest/1641/problem/C

N要素の配列とQ個のクエリが来る。配列の各要素は0か1だが分からない。クエリは以下の3種類。

• L番目からR番目が全て0である。
• L番目からR番目のどれか1つ以上が1である。
• j番目の数が1ならYES、0ならNO、その時点では確定していなければN/Aを出力。

解法

予め全て読み込んでおく。これらを3回全部見る。

クエリ再生1周目

クエリのうち、まずは「L番目からR番目が全て0である」というクエリだけ処理することにする。次の2種類の操作がサポートされた遅延セグメントツリーを用意する。

• L番目からR番目までをX以上ならXに書き換える。
• L番目からR番目までのうち最大値を取り出す。

このセグメントツリーとクエリを使って、配列内の0の各要素について、その値が0と確定した時刻を記録することができる。

クエリ再生2周目

もう一度クエリを最初から全て見る。今度は「L番目からR番目のどれか1つ以上が1である」というクエリだけ処理することにする。L番目からR番目の中の0の要素数が最後までR-L個に満たなければ、このクエリによって1の要素は確定しないのでスルーして良い。L番目からR番目の要素に1の要素が1つだけあり、それがj番目と確定した場合、それ以外の0の要素が確定した時刻の最大値が分かる。その時刻かこのクエリ自体の時刻の大きいほうが、j番目が1と確定した時刻と言える。

クエリ再生3周目

今度は出力するクエリだけ処理することにする。クエリを2周したことで、各要素について、「0だと確定した時刻」「1だと確定した時刻」「何も確定していない」のいずれかが分かっている。指定された要素について、クエリ以前に確定していればYES/NOを、クエリの時点で確定していなければN/Aを出力する。

コード

use std::collections::BTreeSet;

use lazy_segment_tree::LazySegmentTree;

const INF: i64 = 1 << 60;
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let q: usize = sc.read();
    let mut seg = LazySegmentTree::new(
        n,
        || -INF,
        |&left: &i64, &right: &i64| left.max(right),
        |&f: &Option<i64>, &x: &i64| {
            if let Some(f) = f {
                f.min(x)
            } else {
                x
            }
        },
        |&f: &Option<i64>, &g: &Option<i64>| match (f, g) {
            (Some(x), Some(y)) => Some(x.min(y)),
            _ => f.or(g),
        },
        || None,
    );
    for i in 0..n {
        seg.set(i, INF);
    }

    let mut non_zero = (0..n).collect::<BTreeSet<_>>();
    let mut queries = vec![];
    for i in 0..q {
        let t: usize = sc.read();
        if t == 0 {
            let l = sc.usize0();
            let r: usize = sc.read();
            let x: usize = sc.read();
            queries.push((t, l, r, x));
            if x == 0 {
                seg.apply_range(l..r, Some(i as i64));
                while let Some(&x) = non_zero.range(l..r).next() {
                    assert!(non_zero.remove(&x));
                }
            }
        } else {
            let j = sc.usize0();
            queries.push((t, j, 0, 0));
        }
    }

    let mut ans_one = vec![false; n];
    let mut time = vec![INF; n];
    for i in 0..q {
        let (t, l, r, x) = queries[i];
        if t == 0 && x == 1 {
            let min = *non_zero.range(l..).next().unwrap();
            let max = *non_zero.range(..r).next_back().unwrap();
            if min == max {
                let pos = min;
                let mut max = i as i64;
                if l < pos {
                    max = max.max(seg.prod(l..pos));
                }
                if (pos + 1) < r {
                    max = max.max(seg.prod((pos + 1)..r));
                }

                ans_one[pos] = true;
                time[pos] = time[pos].min(max);
            }
        }
    }

    for i in 0..n {
        let zero_time = seg.prod(i..(i + 1));
        if zero_time != INF {
            time[i] = zero_time;
            assert!(!ans_one[i]);
        }
    }

    for i in 0..q {
        let (t, j, _, _) = queries[i];
        if t == 1 {
            if time[j] <= i as i64 {
                if ans_one[j] {
                    sc.write("YES\n");
                } else {
                    sc.write("NO\n");
                }
            } else {
                sc.write("N/A\n");
            }
        }
    }
}
pub mod lazy_segment_tree {
    type Range = std::ops::Range<usize>;

    pub struct LazySegmentTree<S, Op, E, F, Mapping, Composition, Id> {
        n: usize,
        size: usize,
        log: usize,
        data: Vec<S>,
        lazy: Vec<F>,
        op: Op,
        e: E,
        mapping: Mapping,
        composition: Composition,
        id: Id,
    }

    impl<S, Op, E, F, Mapping, Composition, Id> LazySegmentTree<S, Op, E, F, Mapping, Composition, Id>
    where
        S: Clone,
        E: Fn() -> S,
        F: Clone,
        Op: Fn(&S, &S) -> S,
        Mapping: Fn(&F, &S) -> S,
        Composition: Fn(&F, &F) -> F,
        Id: Fn() -> F,
    {
        pub fn new(
            n: usize,
            e: E,
            op: Op,
            mapping: Mapping,
            composition: Composition,
            id: Id,
        ) -> Self {
            let size = n.next_power_of_two() as usize;
            LazySegmentTree {
                n,
                size,
                log: size.trailing_zeros() as usize,
                data: vec![e(); 2 * size],
                lazy: vec![id(); size],
                e,
                op,
                mapping,
                composition,
                id,
            }
        }
        pub fn set(&mut self, mut index: usize, value: S) {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index] = value;
            for i in 1..=self.log {
                self.update(index >> i);
            }
        }

        pub fn get(&mut self, mut index: usize) -> S {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index].clone()
        }

        pub fn prod(&mut self, range: Range) -> S {
            let mut l = range.start;
            let mut r = range.end;
            assert!(l < r && r <= self.n);

            l += self.size;
            r += self.size;

            for i in (1..=self.log).rev() {
                if ((l >> i) << i) != l {
                    self.push(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.push(r >> i);
                }
            }

            let mut sum_l = (self.e)();
            let mut sum_r = (self.e)();
            while l < r {
                if l & 1 != 0 {
                    sum_l = (self.op)(&sum_l, &self.data[l]);
                    l += 1;
                }
                if r & 1 != 0 {
                    r -= 1;
                    sum_r = (self.op)(&self.data[r], &sum_r);
                }
                l >>= 1;
                r >>= 1;
            }

            (self.op)(&sum_l, &sum_r)
        }

        pub fn all_prod(&self) -> S {
            self.data[1].clone()
        }

        pub fn apply(&mut self, mut index: usize, f: F) {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index] = (self.mapping)(&f, &self.data[index]);
            for i in 1..=self.log {
                self.update(index >> i);
            }
        }
        pub fn apply_range(&mut self, range: Range, f: F) {
            let mut l = range.start;
            let mut r = range.end;
            assert!(l <= r && r <= self.n);
            if l == r {
                return;
            }

            l += self.size;
            r += self.size;

            for i in (1..=self.log).rev() {
                if ((l >> i) << i) != l {
                    self.push(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.push((r - 1) >> i);
                }
            }

            {
                let mut l = l;
                let mut r = r;
                while l < r {
                    if l & 1 != 0 {
                        self.all_apply(l, f.clone());
                        l += 1;
                    }
                    if r & 1 != 0 {
                        r -= 1;
                        self.all_apply(r, f.clone());
                    }
                    l >>= 1;
                    r >>= 1;
                }
            }

            for i in 1..=self.log {
                if ((l >> i) << i) != l {
                    self.update(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.update((r - 1) >> i);
                }
            }
        }

        fn update(&mut self, k: usize) {
            self.data[k] = (self.op)(&self.data[2 * k], &self.data[2 * k + 1]);
        }
        fn all_apply(&mut self, k: usize, f: F) {
            self.data[k] = (self.mapping)(&f, &self.data[k]);
            if k < self.size {
                self.lazy[k] = (self.composition)(&f, &self.lazy[k]);
            }
        }
        fn push(&mut self, k: usize) {
            self.all_apply(2 * k, self.lazy[k].clone());
            self.all_apply(2 * k + 1, self.lazy[k].clone());
            self.lazy[k] = (self.id)();
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}