提出 #31084534

---

ソースコード 拡げる

use proconio::{fastout, input};

use tmplib::ds::{BitSet, DecrementalUsizeSet};

#[fastout]
fn main() {
    input! {
        l: usize,
        q: usize,
        cx: [(u32, usize); q],
    }

    let mut bs = BitSet::new(l + 1);
    bs.insert(0);
    bs.insert(l);

    for &(c, x) in &cx {
        if c == 1 {
            bs.insert(x);
        }
    }

    let mut dus = DecrementalUsizeSet::new_with(bs);

    let mut res = vec![];

    for &(c, x) in cx.iter().rev() {
        if c == 1 {
            dus.remove(x);
        } else {
            let lt = dus.less(x).unwrap();
            let gt = dus.greater(x).unwrap();
            res.push(gt - lt);
        }
    }

    for x in res.iter().rev() {
        println!("{}", x);
    }
}

pub mod tmplib {
    pub mod ds {
        pub mod decremental_usize_set {
            use crate::tmplib::ds::BitSet;

            pub struct DecrementalUsizeSet {
                u: usize,
                len: usize,
                small: Vec<u128>,
                large: UnionFind,
            }
            const WORD_SIZE: usize = 128;
            fn bsf(i: u128) -> usize { i.trailing_zeros() as usize }
            fn bsr(i: u128) -> usize {
                WORD_SIZE - 1 - i.leading_zeros() as usize
            }
            impl DecrementalUsizeSet {
                pub fn new_with(bs: BitSet) -> Self {
                    let u = bs.len();
                    let len = bs.count();
                    let mut small = bs.into_inner();
                    small.push(!0);
                    let mut large = UnionFind::new(small.len());
                    for i in 0..small.len() - 1 {
                        if small[i] == 0 {
                            large.unite(i, i + 1);
                        }
                    }
                    Self { u, len, small, large }
                }
                pub fn universe_len(&self) -> usize { self.u }
                pub fn len(&self) -> usize { self.len }
                pub fn is_empty(&self) -> bool { self.len == 0 }
                pub fn contains(&self, i: usize) -> bool {
                    let div = i / WORD_SIZE;
                    let rem = i % WORD_SIZE;
                    div < self.small.len() && self.small[div] >> rem & 1 != 0
                }
                pub fn less(&self, i: usize) -> Option<usize> {
                    if i == 0 { None } else { self.less_equal(i - 1) }
                }
                pub fn less_equal(&self, i: usize) -> Option<usize> {
                    let i = i.min(self.u - 1) + 1;
                    let div = i / WORD_SIZE;
                    let rem = i % WORD_SIZE;
                    let m = self.small[div] & !(!0_u128 << rem);
                    if m != 0 {
                        return Some(div * WORD_SIZE + bsr(m));
                    }
                    let b = self.large.left(div);
                    if b == 0 {
                        None
                    } else {
                        Some((b - 1) * WORD_SIZE + bsr(self.small[b - 1]))
                    }
                }
                pub fn greater(&self, i: usize) -> Option<usize> {
                    if i == self.u { None } else { self.greater_equal(i + 1) }
                }
                pub fn greater_equal(&self, i: usize) -> Option<usize> {
                    let div = i / WORD_SIZE;
                    let rem = i % WORD_SIZE;
                    if div >= self.small.len() {
                        return None;
                    }
                    let m = self.small[div] & !0_u128 << rem;
                    if m != 0 {
                        return Some(div * WORD_SIZE + bsf(m));
                    }
                    let b = self.large.right(div + 1);
                    if b == self.small.len() {
                        None
                    } else {
                        Some(b * WORD_SIZE + bsf(self.small[b]))
                    }
                }
                pub fn remove(&mut self, i: usize) -> bool {
                    let div = i / WORD_SIZE;
                    let rem = i % WORD_SIZE;
                    if div >= self.small.len()
                        || self.small[div] >> rem & 1 == 0
                    {
                        return false;
                    }
                    self.len -= 1;
                    self.small[div] &= !(1_u128 << rem);
                    if self.small[div] == 0 {
                        self.large.unite(div, div + 1);
                    }
                    true
                }
            }
            #[derive(Clone, Copy)]
            enum Item {
                Parent(usize),
                Size(usize),
            }
            use std::cell::RefCell;
            use Item::{Parent, Size};
            struct UnionFind {
                buf: RefCell<Vec<Item>>,
                left: Vec<usize>,
                right: Vec<usize>,
            }
            impl UnionFind {
                pub fn new(n: usize) -> Self {
                    Self {
                        buf: RefCell::new(vec![Size(1); n]),
                        left: (0..n).collect(),
                        right: (0..n).collect(),
                    }
                }
                fn repr(&self, mut i: usize) -> usize {
                    let mut buf = self.buf.borrow_mut();
                    let res = {
                        let mut i = i;
                        while let Parent(ni) = buf[i] {
                            i = ni;
                        }
                        i
                    };
                    while let Parent(ni) = buf[i] {
                        buf[i] = Parent(res);
                        i = ni;
                    }
                    res
                }
                pub fn left(&self, i: usize) -> usize {
                    self.left[self.repr(i)]
                }
                pub fn right(&self, i: usize) -> usize {
                    self.right[self.repr(i)]
                }
                pub fn unite(&mut self, il: usize, ir: usize) {
                    let il = self.repr(il);
                    let ir = self.repr(ir);
                    let mut buf = self.buf.borrow_mut();
                    let (sl, sr) = match (buf[il], buf[ir]) {
                        (Size(sl), Size(sr)) => (sl, sr),
                        _ => unreachable!(),
                    };
                    if sl < sr {
                        buf[ir] = Size(sl + sr);
                        buf[il] = Parent(ir);
                        self.left[ir] = self.left[il];
                    } else {
                        buf[il] = Size(sl + sr);
                        buf[ir] = Parent(il);
                        self.right[il] = self.right[ir];
                    }
                }
            }
        }
        pub use decremental_usize_set::DecrementalUsizeSet;

        pub mod bit_set {
            #[derive(Clone, Eq, PartialEq)]
            pub struct BitSet {
                buf: Vec<u128>,
                len: usize,
                count: usize,
            }
            const WORD_SIZE: usize = 128;
            impl BitSet {
                pub fn new(len: usize) -> Self {
                    let n = (len + WORD_SIZE - 1) / WORD_SIZE;
                    let buf = vec![0; n];
                    Self { buf, len, count: 0 }
                }
                pub fn contains(&self, i: usize) -> bool {
                    let (large, small) = (i / WORD_SIZE, i % WORD_SIZE);
                    *self.buf.get(large).unwrap_or(&0) >> small & 1 != 0
                }
                pub fn insert(&mut self, i: usize) {
                    let (large, small) = (i / WORD_SIZE, i % WORD_SIZE);
                    if self.buf[large] >> small & 1 != 0 {
                        return;
                    }
                    self.buf[large] |= 1 << small;
                    self.count += 1;
                }
                pub fn remove(&mut self, i: usize) {
                    let (large, small) = (i / WORD_SIZE, i % WORD_SIZE);
                    if self.buf[large] >> small & 1 == 0 {
                        return;
                    }
                    *self.buf.get_mut(large).unwrap() &= !(1 << small);
                    self.count -= 1;
                }
                pub fn len(&self) -> usize { self.len }
                pub fn count(&self) -> usize { self.count }
                pub fn into_inner(self) -> Vec<u128> { self.buf }
            }
        }
        pub use bit_set::BitSet;
    }
}

提出情報

ジャッジ結果