Submission #32435428

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use proconio::input;
fn main() {
    input! {
    w: usize,
        n: usize,
    l_r: [(usize, usize); n]
    }
  let mut seg_tree = SegTree::new(vec![0; w], max, |_val, _len, height| height);
  for (l, r) in l_r {
    let height = seg_tree.get_range(l-1, r-1);
    // レンガの範囲の高さは height+1になる
    seg_tree.range_update(l-1, r-1, height+1);
    println!("{}", seg_tree.get_range(l-1, r-1));
  }
}
fn max(a: usize, b: usize) -> usize{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

use proconio::input;

fn main() {
    input! {
		w: usize,
        n: usize,
		l_r: [(usize, usize); n]
    }

	let mut seg_tree = SegTree::new(vec![0; w], max, |_val, _len, height| height);

	for (l, r) in l_r {
		let height = seg_tree.get_range(l-1, r-1);
		// レンガの範囲の高さは height+1になる
		seg_tree.range_update(l-1, r-1, height+1);

		println!("{}", seg_tree.get_range(l-1, r-1));
	}
}

fn max(a: usize, b: usize) -> usize{
	if a < b {
		b
	} else {
		a
	}
}



use std::fmt::Debug;

#[allow(dead_code)]
pub struct SegTree<T, F, L, P>
where
	T: Clone + Copy + Debug,
	F: Fn(T, T) -> T,
	L: Fn(T, usize, P) -> T,
	P: Clone + Copy + Debug,
{
	size: usize,
	values: Vec<Option<T>>,
	ranges: Vec<Option<(usize, usize)>>,
	lazy_params: Vec<Option<P>>,
	operator: F,
	lazy_operator: L,
}

impl<T, F, L, P> SegTree<T, F, L, P>
where
	T: Clone + Copy + Debug,
	F: Fn(T, T) -> T,
	L: Fn(T, usize, P) -> T,
	P: Clone + Copy + Debug,
{
	pub fn new(values: Vec<T>, operator: F, lazy_operator: L) -> Self {
		let size = values.len();
		let tree_size = 2*size.next_power_of_two()-1;
		let vals = vec![None; tree_size];
		let ranges = vec![None; tree_size];

		let mut seg_tree = Self {
			size,
			values: vals,
			ranges,
			lazy_params: vec![None; tree_size],
			operator,
			lazy_operator,
		};

		for i in 0..size {
			let index_of_tree = seg_tree.index_of_tree(i);
			seg_tree.values[index_of_tree] = Some(values[i]);
			seg_tree.ranges[index_of_tree] = Some((i, i));
		}

		for i in 0..seg_tree.index_of_tree(0) {
			// 降順に更新
			let index = seg_tree.index_of_tree(0)-1-i;
			let children_index = seg_tree.children_index(index).unwrap();
			let v1 = seg_tree.values[children_index.0];
			let v2 = seg_tree.values[children_index.1];
			let val = seg_tree.eval(v1, v2);

			let range = if seg_tree.ranges[children_index.0].is_none() {
				None
			} else {
				let range_min = seg_tree.ranges[children_index.0].unwrap().0;
				let range_max = if seg_tree.ranges[children_index.1].is_none() {
					seg_tree.ranges[children_index.0].unwrap().1
				} else {
					seg_tree.ranges[children_index.1].unwrap().1
				};
				Some((range_min, range_max))
			};

			seg_tree.values[index] = val;
			seg_tree.ranges[index] = range;
		}


		seg_tree
	}

	pub fn get(&mut self, index: usize) -> T {
		self.get_range(index, index)
	}

	pub fn get_range(&mut self, left: usize, right: usize) -> T {
		self.get_range_sub(left, right, 0).unwrap()
	}

	fn get_range_sub(&mut self, left: usize, right: usize, index: usize) -> Option<T> {
		if self.ranges[index].is_none() {
			// 指定されたindexに要素が存在しない
			None
		} else {
			let current_range = self.ranges[index].unwrap();

			// 遅延評価
			self.lazy_eval(index);

			if self.children_index(index).is_none() {
				// 葉
				if left <= current_range.0 && current_range.0 <= right {
					self.values[index]
				} else {
					None
				}
			} else if left <= current_range.0 && current_range.1 <= right {
				// 現在の範囲が覆われている場合
				// 現在の範囲での値を返す
				self.values[index]
			} else if right < current_range.0 || current_range.1 < left {
				// 現在の範囲と共通部分がない
				None
			} else {
				// 現在の範囲と共通部分がある場合
				// 子供も調べる
				let val_left = self.get_range_sub(left, right, self.children_index(index).unwrap().0);
				let val_right = self.get_range_sub(left, right, self.children_index(index).unwrap().1);
				self.eval(
					val_left,
					val_right,
				)
			}
		}
	}

	pub fn update(&mut self, index: usize, value: T) {
		// 遅延評価を実行する
		self.get(index);

		let mut index = self.index_of_tree(index);
		self.values[index] = Some(value);

		while !self.parent_index(index).is_none() {
			index = self.parent_index(index).unwrap();
			let children = self.children_index(index).unwrap();
			self.values[index] = self.eval(self.values[children.0], self.values[children.1]);
		}
	}

	pub fn range_update(&mut self, left: usize, right: usize, params: P) {
		if let Some(_) = self.lazy_params[0] {
			// 遅延更新が残っているので伝播させる
			self.get_range(0, self.size-1);
		}

		self.range_update_sub(left, right, params, 0);
	}

	fn range_update_sub(&mut self, left: usize, right: usize, params: P, index: usize) {
		if let Some(current_range) = self.ranges[index] {
			if right < current_range.0 || current_range.1 < left {
				// 範囲外なら何もしない
				return;
			} else if left <= current_range.0 && current_range.1 <= right {
				// 完全に覆われているなら遅延配列に値を入れて評価
				self.lazy_params[index] = Some(params);
				self.lazy_eval(index);
			} else {
				// 子ノードから計算済みの値をもらう
				if let Some((index_c1, index_c2)) = self.children_index(index) {
					let range_c1 = self.ranges[index_c1];
					let range_c2 = self.ranges[index_c2];

					if let Some(range_c1) = range_c1 {
						let intersection_left = if left <= range_c1.0 {
							range_c1.0
						} else {
							left
						};
						let intersection_right = if right <= range_c1.1 {
							right
						} else {
							range_c1.1
						};

						if intersection_left <=  intersection_right {
							// 共通部分がある
							self.range_update_sub(intersection_left, intersection_right, params, index_c1);
						}
					}

					if let Some(range_c2) = range_c2 {
						let intersection_left = if left <= range_c2.0 {
							range_c2.0
						} else {
							left
						};
						let intersection_right = if right <= range_c2.1 {
							right
						} else {
							range_c2.1
						};
						if intersection_left <=  intersection_right {
							// 共通部分がある
							self.range_update_sub(intersection_left, intersection_right, params, index_c2);
						}
					}

					self.values[index] = self.eval(self.values[index_c1], self.values[index_c2]);
				}
			}
		}

	}

	fn lazy_eval(&mut self, index: usize) {
		let current_range = self.ranges[index].unwrap();
		if let Some(params) = self.lazy_params[index] {
			self.values[index] = Some((self.lazy_operator)(self.values[index].unwrap(), current_range.1 - current_range.0 + 1, params));
			self.lazy_params[index] = None;

			if let Some((index_c1, index_c2)) = self.children_index(index) {
				// 子に伝播する
				let range_c1 = self.ranges[index_c1];
				let range_c2 = self.ranges[index_c2];

				if let Some(_) = range_c1 {
					self.lazy_params[index_c1] = Some(params);
				}

				if let Some(_) = range_c2 {
					self.lazy_params[index_c2] = Some(params);
				}
			}
		}
	}

	fn eval(&self, v1: Option<T>, v2: Option<T>) -> Option<T> {
		if v1.is_none() {
			if v2.is_none() {
				None
			} else {
				v2
			}
		} else {
			if v2.is_none() {
				v1
			} else {
				Some((self.operator)(v1.unwrap(), v2.unwrap()))
			}
		}
	}

	fn children_index(&self, index: usize) -> Option<(usize, usize)> {
		if index >= self.values.len()/2 {
			None
		} else {
			Some((2*index+1, 2*index+2))
		}
	}

	fn parent_index(&self, index: usize) -> Option<usize> {
		if index == 0 {
			None
		} else {
			Some((index-1)/2)
		}
	}

	fn index_of_tree(&self, index: usize) -> usize {
		self.values.len()/2+index
	}
}


impl<T, F, L, P>Debug for SegTree<T, F, L, P>
where
	T: Clone + Copy + Debug,
	F: Fn(T, T) -> T,
	L: Fn(T, usize, P) -> T,
	P: Clone + Copy + Debug,
{
	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
		for i in 0..self.values.len() {
			if let Some(range) = self.ranges[i] {
				f.write_fmt(format_args!("[{}, {}] val: {:?}, lazy: {:?}\n", range.0, range.1, self.values[i], self.lazy_params[i])).unwrap();
			}
		}
		Ok(())
	}
}

Submission Info

Judge Result