//https://github.com/rust-lang-ja/ac-library-rs pub mod fenwicktree { use std::ops::{Bound, RangeBounds}; // Reference: https://en.wikipedia.org/wiki/Fenwick_tree pub struct FenwickTree { n: usize, ary: Vec, e: T, } impl> FenwickTree { pub fn new(n: usize, e: T) -> Self { FenwickTree { n, ary: vec![e.clone(); n], e, } } pub fn accum(&self, mut idx: usize) -> T { let mut sum = self.e.clone(); while idx > 0 { sum += self.ary[idx - 1].clone(); idx &= idx - 1; } sum } /// performs data[idx] += val; pub fn add(&mut self, mut idx: usize, val: U) where T: std::ops::AddAssign, { let n = self.n; idx += 1; while idx <= n { self.ary[idx - 1] += val.clone(); idx += idx & idx.wrapping_neg(); } } /// Returns data[l] + ... + data[r - 1]. pub fn sum(&self, range: R) -> T where T: std::ops::Sub, R: RangeBounds, { let r = match range.end_bound() { Bound::Included(r) => r + 1, Bound::Excluded(r) => *r, Bound::Unbounded => self.n, }; let l = match range.start_bound() { Bound::Included(l) => *l, Bound::Excluded(l) => l + 1, Bound::Unbounded => return self.accum(r), }; self.accum(r) - self.accum(l) } } #[cfg(test)] mod tests { use super::*; use std::ops::Bound::*; #[test] fn fenwick_tree_works() { let mut bit = FenwickTree::new(5, 0i64); // [1, 2, 3, 4, 5] for i in 0..5 { bit.add(i, i as i64 + 1); } assert_eq!(bit.sum(0..5), 15); assert_eq!(bit.sum(0..4), 10); assert_eq!(bit.sum(1..3), 5); assert_eq!(bit.sum(..), 15); assert_eq!(bit.sum(..2), 3); assert_eq!(bit.sum(..=2), 6); assert_eq!(bit.sum(1..), 14); assert_eq!(bit.sum(1..=3), 9); assert_eq!(bit.sum((Excluded(0), Included(2))), 5); } } } use fenwicktree::*; pub mod compression { pub struct Compression { pub id: std::collections::BTreeMap, pub rev: Vec, } impl Compression { pub fn new() -> Self { Self { id: std::collections::BTreeMap::new(), rev: vec![], } } pub fn add(&mut self, key: T) { self.id.entry(key).or_insert(0); } pub fn compress(mut self) -> (std::collections::BTreeMap, Vec) { self.rev = vec![]; for (k, v) in self.id.iter_mut() { *v = self.rev.len(); self.rev.push(*k); } (self.id, self.rev) } } } pub mod scanner { pub struct Scanner { buf: Vec, } impl Scanner { pub fn new() -> Self { Self { buf: vec![] } } pub fn new_from(source: &str) -> Self { let source = String::from(source); let buf = Self::split(source); Self { buf } } pub fn next(&mut self) -> T { loop { if let Some(x) = self.buf.pop() { return x.parse().ok().expect(""); } let mut source = String::new(); std::io::stdin().read_line(&mut source).expect(""); self.buf = Self::split(source); } } fn split(source: String) -> Vec { source .split_whitespace() .rev() .map(String::from) .collect::>() } } } use crate::FenwickTree; use crate::{compression::Compression, scanner::Scanner}; use std::{collections::BTreeMap, io::Write}; fn main() { let mut scanner = Scanner::new(); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); let t: usize = 1; for _ in 0..t { solve(&mut scanner, &mut out); } } fn name_id(s: String) -> usize { let mut res = 0; let mut b = 1; for c in s.chars().rev() { let now = c as usize - 'a' as usize + 1; res += now * b; b *= 27; } res } fn solve(scanner: &mut Scanner, out: &mut std::io::BufWriter) { let n: usize = scanner.next(); let xlr = (0..n) .map(|_| { ( name_id(scanner.next::()), scanner.next::(), scanner.next::(), ) }) .collect::>(); let q: usize = scanner.next(); let qs = (0..q) .map(|_| { let qt = scanner.next::(); let (x, t, l, r) = if qt == 1 { ( name_id(scanner.next::()), scanner.next::(), 0, 0, ) } else if qt == 2 { (0, scanner.next::(), 0, 0) } else { ( name_id(scanner.next::()), 0, scanner.next::(), scanner.next::(), ) }; (qt, x, t, l, r) }) .collect::>(); let mut map = BTreeMap::new(); for i in 0..n { let (x, l, r) = xlr[i]; map.entry(x).or_insert(vec![]).push((0, 0, 0, l, r)); } for i in 0..q { let (qt, x, t, l, r) = qs[i]; if qt == 1 || qt == 3 { map.entry(x).or_insert(vec![]).push((qt, i, t, l, r)); } } let mut ans = vec![0; q]; for (_, list) in map.iter() { let mut compression = Compression::new(); compression.add(0); compression.add(1e9 as usize + 5); for &(_, _, t, l, r) in list.iter() { compression.add(t); compression.add(l); compression.add(r); } let (id, _) = compression.compress(); let mut bit = FenwickTree::new(id.len(), 0isize); for &(qt, qi, t, l, r) in list.iter() { if qt == 0 || qt == 3 { bit.add(id[&l], 1); bit.add(id[&r] + 1, -1); } else { ans[qi] = bit.sum(0..=id[&t]); } } } let mut compression = Compression::new(); compression.add(0); compression.add(1e9 as usize + 5); for &(_, l, r) in xlr.iter() { compression.add(l); compression.add(r); } for &(_, _, t, l, r) in qs.iter() { compression.add(t); compression.add(l); compression.add(r); } let (id, _) = compression.compress(); let mut bit = FenwickTree::new(id.len(), 0isize); for &(_, l, r) in xlr.iter() { bit.add(id[&l], 1); bit.add(id[&r] + 1, -1); } for qi in 0..q { let (qt, _, t, l, r) = qs[qi]; if qt == 2 { ans[qi] = bit.sum(0..=id[&t]); } if qt == 3 { bit.add(id[&l], 1); bit.add(id[&r] + 1, -1); } } for qi in 0..q { let qt = qs[qi].0; if qt == 1 { if ans[qi] > 0 { writeln!(out, "Yes").unwrap(); } else { writeln!(out, "No").unwrap(); } } if qt == 2 { writeln!(out, "{}", ans[qi]).unwrap(); } } }