#824792 (Rust) No.2160 みたりのDominator

• 問題: No.2160 みたりのDominator
• ユーザー: akakimidori
• 提出日時: 2022-12-11 23:08:36
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 144 ms / 2,000 ms
• コード長: 17,809 bytes
• コンパイル時間: 23,933 ms
• コンパイル使用メモリ: 383,972 KB
• 実行使用メモリ: 50,572 KB
• 最終ジャッジ日時: 2024-10-15 18:05:11
• 合計ジャッジ時間: 31,739 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	79 ms; 34,208 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	1 ms; 5,248 KB
testcase_13	AC	1 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	1 ms; 5,248 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	AC	1 ms; 5,248 KB
testcase_19	AC	2 ms; 5,248 KB
testcase_20	AC	1 ms; 5,248 KB
testcase_21	AC	1 ms; 5,248 KB
testcase_22	AC	1 ms; 5,248 KB
testcase_23	AC	1 ms; 5,248 KB
testcase_24	AC	1 ms; 5,248 KB
testcase_25	AC	1 ms; 5,248 KB
testcase_26	AC	1 ms; 5,248 KB
testcase_27	AC	2 ms; 5,248 KB
testcase_28	AC	1 ms; 5,248 KB
testcase_29	AC	1 ms; 5,248 KB
testcase_30	AC	1 ms; 5,248 KB
testcase_31	AC	1 ms; 5,248 KB
testcase_32	AC	1 ms; 5,248 KB
testcase_33	AC	1 ms; 5,248 KB
testcase_34	AC	20 ms; 39,936 KB
testcase_35	AC	1 ms; 5,248 KB
testcase_36	AC	1 ms; 5,248 KB
testcase_37	AC	1 ms; 5,248 KB
testcase_38	AC	1 ms; 5,248 KB
testcase_39	AC	1 ms; 5,248 KB
testcase_40	AC	126 ms; 35,928 KB
testcase_41	AC	96 ms; 34,804 KB
testcase_42	AC	69 ms; 21,036 KB
testcase_43	AC	97 ms; 29,376 KB
testcase_44	AC	112 ms; 34,952 KB
testcase_45	AC	111 ms; 34,428 KB
testcase_46	AC	96 ms; 32,784 KB
testcase_47	AC	52 ms; 19,392 KB
testcase_48	AC	51 ms; 26,588 KB
testcase_49	AC	56 ms; 30,532 KB
testcase_50	AC	44 ms; 29,800 KB
testcase_51	AC	76 ms; 22,772 KB
testcase_52	AC	91 ms; 32,816 KB
testcase_53	AC	101 ms; 34,712 KB
testcase_54	AC	59 ms; 20,440 KB
testcase_55	AC	144 ms; 42,608 KB
testcase_56	AC	129 ms; 38,028 KB
testcase_57	AC	100 ms; 39,984 KB
testcase_58	AC	50 ms; 33,408 KB
testcase_59	AC	101 ms; 41,380 KB
testcase_60	AC	121 ms; 50,572 KB
testcase_61	AC	91 ms; 39,320 KB
testcase_62	AC	107 ms; 49,032 KB
testcase_63	AC	119 ms; 43,440 KB
testcase_64	AC	116 ms; 41,932 KB
testcase_65	AC	45 ms; 27,436 KB
testcase_66	AC	27 ms; 18,432 KB
testcase_67	AC	26 ms; 18,900 KB
testcase_68	AC	48 ms; 31,616 KB
testcase_69	AC	35 ms; 23,808 KB
testcase_70	AC	51 ms; 31,824 KB
testcase_71	AC	34 ms; 24,832 KB
testcase_72	AC	46 ms; 34,356 KB
testcase_73	AC	51 ms; 30,308 KB
testcase_74	AC	51 ms; 29,184 KB
testcase_75	AC	11 ms; 20,264 KB
testcase_76	AC	9 ms; 18,020 KB
testcase_77	AC	49 ms; 37,132 KB
testcase_78	AC	53 ms; 39,452 KB
testcase_79	AC	8 ms; 12,520 KB
testcase_80	AC	9 ms; 14,376 KB
testcase_81	AC	23 ms; 25,392 KB
testcase_82	AC	17 ms; 26,368 KB
testcase_83	AC	63 ms; 31,324 KB
61_evil_bias_nocross_01.txt	AC	103 ms; 35,768 KB
61_evil_bias_nocross_02.txt	AC	106 ms; 34,828 KB
61_evil_bias_nocross_03.txt	AC	65 ms; 20,592 KB
61_evil_bias_nocross_04.txt	AC	74 ms; 30,040 KB
61_evil_bias_nocross_05.txt	AC	94 ms; 35,488 KB
61_evil_bias_nocross_06.txt	AC	99 ms; 35,608 KB
61_evil_bias_nocross_07.txt	AC	65 ms; 22,564 KB
61_evil_bias_nocross_08.txt	AC	97 ms; 32,616 KB
61_evil_bias_nocross_09.txt	AC	113 ms; 33,992 KB
61_evil_bias_nocross_10.txt	AC	54 ms; 20,572 KB
61_evil_bias_nocross_11.txt	AC	75 ms; 28,876 KB
61_evil_bias_nocross_12.txt	AC	86 ms; 32,368 KB

コンパイルメッセージ

warning: unused import: `std::io::Write`
 --> src/main.rs:2:5
  |
2 | use std::io::Write;
  |     ^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: type alias `Map` is never used
 --> src/main.rs:4:6
  |
4 | type Map<K, V> = BTreeMap<K, V>;
  |      ^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: type alias `Set` is never used
 --> src/main.rs:5:6
  |
5 | type Set<T> = BTreeSet<T>;
  |      ^^^

warning: type alias `Deque` is never used
 --> src/main.rs:6:6
  |
6 | type Deque<T> = VecDeque<T>;
  |      ^^^^^

ソースコード

use std::collections::*;
use std::io::Write;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    input! {
        n: [usize; 3],
        m: usize,
        e: [(usize1, usize1); m],
    }
    let v = n.iter().sum::<usize>() + 2;
    let s = v - 2;
    let t = v - 1;
    let mut dsu = DSU::new(v);
    let mut dp = vec![[(v, 0); 3]; v];
    for i in 0..n[0] {
        dp[i][0] = (i, i);
    }
    for i in 0..n[1] {
        dp[n[0] + i][1] = (i, i);
    }
    for i in 0..n[2] {
        dp[n[0] + n[1] + i][2] = (i, i);
    }
    let mut edge = vec![];
    for &(mut a, mut b) in e.iter() {
        if a > b {
            std::mem::swap(&mut a, &mut b);
        }
        if let Some((a, b)) = dsu.unite(a, b) {
            let c = std::mem::take(&mut dp[b]);
            for (a, b) in dp[a].iter_mut().zip(c.iter()) {
                a.0 = a.0.min(b.0);
                a.1 = a.1.max(b.1);
            }
        }
        if b >= s {
            continue;
        }
        let x = n
            .iter()
            .position(|n| {
                a < *n || {
                    a -= *n;
                    false
                }
            })
            .unwrap();
        let y = n
            .iter()
            .position(|n| {
                b < *n || {
                    b -= *n;
                    false
                }
            })
            .unwrap();
        edge.push((x, y, a, b));
    }
    if dsu.same(s, t) {
        println!("0");
        return;
    }
    let n_max = *n.iter().max().unwrap();
    let mut ban = vec![vec![0; n_max + 2]; 3];
    let mut query = vec![vec![]; 3];
    let mut seg =
        segment_tree::RUPQ::new(n[1] + 1, (0, n[2] + 1), |a, b| (a.0.max(b.0), a.1.min(b.1)));
    for &(x, y, a, b) in edge.iter() {
        if x == y {
            ban[x][a + 1] += 1;
            ban[x][b + 1] -= 1;
            continue;
        }
        if x == 0 {
            query[y].push((a, b));
        } else {
            seg.update(0, a + 1, (0, b + 1));
            seg.update(a + 1, n[1] + 1, (b + 1, n[2] + 1));
        }
    }
    for (i, ban) in ban.iter_mut().enumerate() {
        for i in 1..ban.len() {
            ban[i] += ban[i - 1];
        }
        let a = dp[dsu.root(s)];
        if a[i].0 != v {
            let t = a[i].1;
            for j in 0..=t {
                ban[j] += 1;
            }
        }
        let b = dp[dsu.root(t)];
        if b[i].0 != v {
            let s = b[i].0;
            for j in (s + 1)..ban.len() {
                ban[j] += 1;
            }
        }
    }
    let mut range = vec![vec![0], vec![0], vec![0]];
    for (query, range) in query.iter_mut().zip(range.iter_mut()) {
        query.sort_by_key(|p| p.0);
        for &(_, b) in query.iter() {
            let v = (b + 1).max(*range.last().unwrap());
            range.push(v);
        }
    }
    let mut op = vec![];
    let mut up = [0, n[1] + 2, n[2] + 2];
    for i in (0..=n[0]).rev() {
        if ban[0][i] > 0 {
            continue;
        }
        for p in 1..3 {
            let up = &mut up[p];
            let query = &mut query[p];
            let range = &mut range[p];
            while query.last().map_or(false, |p| p.0 >= i) {
                let (_, b) = query.pop().unwrap();
                range.pop();
                *up = std::cmp::min(*up, b + 1);
            }
        }
        let (l, r) = (*range[1].last().unwrap(), up[1]);
        let (d, u) = (*range[2].last().unwrap(), up[2]);
        if l < r && d < u {
            op.push((l, !0, d, u));
            op.push((r, 1, d, u));
        }
    }
    op.sort_by_key(|p| p.0);
    let mut laz = LazySegmentTree::build(
        (0..=n[2]).map(|x| if ban[2][x] > 0 { (0, 0) } else { (1, 0) }),
        n[2] + 2,
        R,
    );
    let mut x = 0;
    let mut ans = 0usize;
    for (pos, sign, d, u) in op {
        while x < pos {
            if ban[1][x] == 0 && x <= n[1] {
                let (s, t) = seg.find(x);
                if s < t {
                    laz.update(s, t, 1);
                }
            }
            x += 1;
        }
        ans += sign * laz.find(d, u).1;
    }
    println!("{}", ans);
}

struct R;
impl TE for R {
    type T = (usize, usize);
    type E = usize;
    fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T {
        (l.0 + r.0, l.1 + r.1)
    }
    fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T {
        (x.0, x.1 + x.0 * *f)
    }
    fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E {
        *g + *h
    }
    fn e(&self) -> Self::T {
        (0, 0)
    }
    fn id(&self) -> Self::E {
        0
    }
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
//---------- begin union_find ----------
pub struct DSU {
    p: Vec<i32>,
}
impl DSU {
    pub fn new(n: usize) -> DSU {
        assert!(n < std::i32::MAX as usize);
        DSU { p: vec![-1; n] }
    }
    pub fn init(&mut self) {
        self.p.iter_mut().for_each(|p| *p = -1);
    }
    pub fn root(&self, mut x: usize) -> usize {
        assert!(x < self.p.len());
        while self.p[x] >= 0 {
            x = self.p[x] as usize;
        }
        x
    }
    pub fn same(&self, x: usize, y: usize) -> bool {
        assert!(x < self.p.len() && y < self.p.len());
        self.root(x) == self.root(y)
    }
    pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
        assert!(x < self.p.len() && y < self.p.len());
        let mut x = self.root(x);
        let mut y = self.root(y);
        if x == y {
            return None;
        }
        if self.p[x] > self.p[y] {
            std::mem::swap(&mut x, &mut y);
        }
        self.p[x] += self.p[y];
        self.p[y] = x as i32;
        Some((x, y))
    }
    pub fn parent(&self, x: usize) -> Option<usize> {
        assert!(x < self.p.len());
        let p = self.p[x];
        if p >= 0 {
            Some(p as usize)
        } else {
            None
        }
    }
    pub fn sum<F>(&self, mut x: usize, mut f: F) -> usize
    where
        F: FnMut(usize),
    {
        while let Some(p) = self.parent(x) {
            f(x);
            x = p;
        }
        x
    }
    pub fn size(&self, x: usize) -> usize {
        assert!(x < self.p.len());
        let r = self.root(x);
        (-self.p[r]) as usize
    }
}
//---------- end union_find ----------
// ---------- begin chmin, chmax ----------
pub trait ChangeMinMax {
    fn chmin(&mut self, x: Self) -> bool;
    fn chmax(&mut self, x: Self) -> bool;
}

impl<T: PartialOrd> ChangeMinMax for T {
    fn chmin(&mut self, x: Self) -> bool {
        *self > x && {
            *self = x;
            true
        }
    }
    fn chmax(&mut self, x: Self) -> bool {
        *self < x && {
            *self = x;
            true
        }
    }
}
// ---------- end chmin, chmax ----------
// ---------- begin SegmentTree Range update Point query ----------
mod segment_tree {
    pub struct RUPQ<T, F> {
        size: usize,
        bit: usize,
        data: Vec<T>,
        e: T,
        op: F,
    }
    impl<T, F> RUPQ<T, F>
    where
        T: Clone,
        F: Fn(&T, &T) -> T,
    {
        pub fn new(size: usize, e: T, op: F) -> Self {
            let size = size.next_power_of_two();
            let bit = size.trailing_zeros() as usize;
            Self {
                size,
                bit,
                data: vec![e.clone(); 2 * size],
                e,
                op,
            }
        }
        pub fn find(&self, x: usize) -> T {
            assert!(x < self.size);
            let mut x = x + self.size;
            let mut ans = self.data[x].clone();
            while x > 1 {
                x >>= 1;
                ans = (self.op)(&ans, &self.data[x]);
            }
            ans
        }
        fn propagate(&mut self, x: usize) {
            let f = std::mem::replace(&mut self.data[x], self.e.clone());
            self.data[2 * x] = (self.op)(&self.data[2 * x], &f);
            self.data[2 * x + 1] = (self.op)(&self.data[2 * x + 1], &f);
        }
        pub fn update(&mut self, l: usize, r: usize, f: T) {
            assert!(l <= r && r <= self.size);
            if l == r {
                return;
            }
            let mut l = l + self.size;
            let mut r = r + self.size;
            for i in (1..=self.bit).rev() {
                if (l >> i) << i != l {
                    self.propagate(l >> i);
                }
                if (r >> i) << i != r {
                    self.propagate((r - 1) >> i);
                }
            }
            while l < r {
                if l & 1 == 1 {
                    self.data[l] = (self.op)(&self.data[l], &f);
                    l += 1;
                }
                if r & 1 == 1 {
                    r -= 1;
                    self.data[r] = (self.op)(&self.data[r], &f);
                }
                l >>= 1;
                r >>= 1;
            }
        }
    }
}
// ---------- end SegmentTree Range update Point query ----------
// ---------- begin segment tree Point Update Range Query ----------
pub struct SegmentTreePURQ<T, F> {
    n: usize,
    size: usize,
    data: Vec<T>,
    e: T,
    op: F,
}

impl<T, F> SegmentTreePURQ<T, F>
where
    T: Clone,
    F: Fn(&T, &T) -> T,
{
    pub fn new(n: usize, e: T, op: F) -> Self {
        assert!(n > 0);
        let size = n.next_power_of_two();
        let data = vec![e.clone(); 2 * size];
        SegmentTreePURQ {
            n,
            size,
            data,
            e,
            op,
        }
    }
    pub fn update_tmp(&mut self, x: usize, v: T) {
        assert!(x < self.n);
        self.data[x + self.size] = v;
    }
    pub fn update_all(&mut self) {
        for i in (1..self.size).rev() {
            self.data[i] = (self.op)(&self.data[2 * i], &self.data[2 * i + 1]);
        }
    }
    pub fn update(&mut self, x: usize, v: T) {
        assert!(x < self.n);
        let mut x = x + self.size;
        self.data[x] = v;
        x >>= 1;
        while x > 0 {
            self.data[x] = (self.op)(&self.data[2 * x], &self.data[2 * x + 1]);
            x >>= 1;
        }
    }
    pub fn find(&self, l: usize, r: usize) -> T {
        assert!(l <= r && r <= self.n);
        if l == r {
            return self.e.clone();
        }
        let mut l = self.size + l;
        let mut r = self.size + r;
        let mut x = self.e.clone();
        let mut y = self.e.clone();
        while l < r {
            if l & 1 == 1 {
                x = (self.op)(&x, &self.data[l]);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                y = (self.op)(&self.data[r], &y);
            }
            l >>= 1;
            r >>= 1;
        }
        (self.op)(&x, &y)
    }
    pub fn max_right<P>(&self, l: usize, f: P) -> usize
    where
        P: Fn(&T) -> bool,
    {
        assert!(l <= self.n);
        assert!(f(&self.e));
        if l == self.n {
            return self.n;
        }
        let mut l = l + self.size;
        let mut sum = self.e.clone();
        while {
            l >>= l.trailing_zeros();
            let v = (self.op)(&sum, &self.data[l]);
            if !f(&v) {
                while l < self.size {
                    l <<= 1;
                    let v = (self.op)(&sum, &self.data[l]);
                    if f(&v) {
                        sum = v;
                        l += 1;
                    }
                }
                return l - self.size;
            }
            sum = v;
            l += 1;
            l.count_ones() > 1
        } {}
        self.n
    }
    pub fn min_left<P>(&self, r: usize, f: P) -> usize
    where
        P: Fn(&T) -> bool,
    {
        assert!(r <= self.n);
        assert!(f(&self.e));
        if r == 0 {
            return 0;
        }
        let mut r = r + self.size;
        let mut sum = self.e.clone();
        while {
            r -= 1;
            while r > 1 && r & 1 == 1 {
                r >>= 1;
            }
            let v = (self.op)(&self.data[r], &sum);
            if !f(&v) {
                while r < self.size {
                    r = 2 * r + 1;
                    let v = (self.op)(&self.data[r], &sum);
                    if f(&v) {
                        sum = v;
                        r -= 1;
                    }
                }
                return r + 1 - self.size;
            }
            sum = v;
            (r & (!r + 1)) != r
        } {}
        0
    }
}
// ---------- end segment tree Point Update Range Query ----------
// ---------- begin Lazy Segment Tree ----------
pub trait TE {
    type T: Clone;
    type E: Clone;
    fn fold(&self, l: &Self::T, r: &Self::T) -> Self::T;
    fn eval(&self, x: &Self::T, f: &Self::E) -> Self::T;
    fn merge(&self, g: &Self::E, h: &Self::E) -> Self::E;
    fn e(&self) -> Self::T;
    fn id(&self) -> Self::E;
}

pub struct LazySegmentTree<R: TE> {
    n: usize,
    size: usize,
    bit: u32,
    op: R,
    data: Vec<(R::T, R::E)>,
}

impl<R: TE> LazySegmentTree<R> {
    pub fn new(n: usize, op: R) -> Self {
        assert!(n > 0);
        let size = n.next_power_of_two();
        let bit = size.trailing_zeros();
        let data = vec![(op.e(), op.id()); 2 * size];
        Self {
            n,
            size,
            bit,
            op,
            data,
        }
    }
    pub fn build<I>(init: I, n: usize, op: R) -> Self
    where
        I: Iterator<Item = R::T>,
    {
        let mut seg = Self::new(n, op);
        for (data, ini) in seg.data[seg.size..].iter_mut().zip(init) {
            data.0 = ini;
        }
        for i in (1..seg.size).rev() {
            seg.pull(i);
        }
        seg
    }
    pub fn update(&mut self, l: usize, r: usize, f: R::E) {
        assert!(l <= r && r <= self.n);
        if l == r {
            return;
        }
        self.push_range(l, r);
        let mut s = l + self.size;
        let mut t = r + self.size;
        while s < t {
            if s & 1 == 1 {
                self.apply(s, &f);
                s += 1;
            }
            if t & 1 == 1 {
                t -= 1;
                self.apply(t, &f);
            }
            s >>= 1;
            t >>= 1;
        }
        let l = l + self.size;
        let r = r + self.size;
        for k in 1..=self.bit {
            if (l >> k) << k != l {
                self.pull(l >> k);
            }
            if (r >> k) << k != r {
                self.pull((r - 1) >> k);
            }
        }
    }
    pub fn find(&mut self, l: usize, r: usize) -> R::T {
        assert!(l <= r && r <= self.n);
        if l == r {
            return self.op.e();
        }
        self.push_range(l, r);
        let mut l = l + self.size;
        let mut r = r + self.size;
        let mut p = self.op.e();
        let mut q = self.op.e();
        while l < r {
            if l & 1 == 1 {
                p = self.op.fold(&p, &self.data[l].0);
                l += 1;
            }
            if r & 1 == 1 {
                r -= 1;
                q = self.op.fold(&self.data[r].0, &q);
            }
            l >>= 1;
            r >>= 1;
        }
        self.op.fold(&p, &q)
    }
    pub fn set_at(&mut self, x: usize, v: R::T) {
        assert!(x < self.n);
        let x = x + self.size;
        for k in (1..=self.bit).rev() {
            self.push(x >> k);
        }
        self.data[x].0 = v;
        for k in 1..=self.bit {
            self.pull(x >> k);
        }
    }
    fn push_range(&mut self, l: usize, r: usize) {
        let l = l + self.size;
        let r = r + self.size;
        for k in (1..=self.bit).rev() {
            if (l >> k) << k != l {
                self.push(l >> k);
            }
            if (r >> k) << k != r {
                self.push((r - 1) >> k);
            }
        }
    }
    fn apply(&mut self, x: usize, f: &R::E) {
        self.data[x].0 = self.op.eval(&self.data[x].0, f);
        self.data[x].1 = self.op.merge(&self.data[x].1, f);
    }
    fn push(&mut self, x: usize) {
        let f = std::mem::replace(&mut self.data[x].1, self.op.id());
        self.apply(2 * x, &f);
        self.apply(2 * x + 1, &f);
    }
    fn pull(&mut self, x: usize) {
        self.data[x].0 = self.op.fold(&self.data[2 * x].0, &self.data[2 * x + 1].0);
    }
}
// ---------- end Lazy Segment Tree ----------