#![allow(non_snake_case, unused_imports, unused_must_use)] use std::io::{self, prelude::*}; use std::str; fn main() { let (stdin, stdout) = (io::stdin(), io::stdout()); let mut scan = Scanner::new(stdin.lock()); let mut out = io::BufWriter::new(stdout.lock()); macro_rules! input { ($T: ty) => { scan.token::<$T>() }; ($T: ty, $N: expr) => { (0..$N).map(|_| scan.token::<$T>()).collect::>() }; } let N = input!(usize); let Q = input!(usize); let IST = (0..Q) .map(|_| (input!(usize) - 1, input!(usize), input!(usize))) .collect::>(); let mut point = vec![0.0; 100_010]; { let mut stree = SegmentTree::new(100_010, |x, y| x + y, 0); for &(_, s, t) in IST.iter() { stree.apply(s, t, 1); } for i in 0..100_010 { let c = stree.get(i); point[i] = 1.0 / c as f64; } struct SegmentTree { size: usize, tree: Vec, op: fn(T, T) -> T, } impl SegmentTree { fn new(n: usize, op: fn(T, T) -> T, id: T) -> Self { Self { size: n, tree: vec![id; n + n], op: op, } } fn get(&self, mut p: usize) -> T { p += self.size; let mut ret = self.tree[p]; while p > 1 { p >>= 1; ret = (self.op)(ret, self.tree[p]); } ret } fn apply(&mut self, l: usize, r: usize, val: T) { let mut il = l + self.size; let mut ir = r + self.size; while il < ir { if il & 1 == 1 { self.tree[il] = (self.op)(self.tree[il], val); il += 1; } if ir & 1 == 1 { ir -= 1; self.tree[ir] = (self.op)(self.tree[ir], val); } il >>= 1; ir >>= 1; } } } } { let mut stree = Segmenttree::new(100_010, |x, y| x + y, 0.0); for i in 0..100_010 { stree.insert(i, point[i]); } let mut ans = vec![0.0; N]; for (i, s, t) in IST { let dv = stree.get(s, t); ans[i] += dv; } writeln!( out, "{}", ans.iter() .map(|x| x.to_string()) .collect::>() .join("\n") ); #[derive(Clone)] struct Segmenttree { len: usize, tree: Vec, op: fn(T, T) -> T, id: T, } impl Segmenttree { /// 新規生成 fn new(l: usize, op: fn(T, T) -> T, id: T) -> Self { return Segmenttree { len: l, tree: vec![id; l * 2], op: op, id: id, }; } /// p 番目の要素を v に更新する. fn insert(&mut self, p: usize, v: T) { let mut pos = p; pos += self.len; self.tree[pos] = v; while pos > 1 { pos >>= 1; self.tree[pos] = (self.op)(self.tree[pos << 1], self.tree[pos << 1 | 1]); } } /// p 番目の要素を取得する. fn get_point(&self, p: usize) -> T { return self.tree[p + self.len]; } /// [l, r) の要素の総積を取得する. fn get(&self, l: usize, r: usize) -> T { let (mut pl, mut pr) = (l + self.len, r + self.len); let (mut vl, mut vr) = (self.id, self.id); while pl < pr { if pl & 1 == 1 { vl = (self.op)(vl, self.tree[pl]); pl += 1; } if pr & 1 == 1 { pr -= 1; vr = (self.op)(self.tree[pr], vr); } pl >>= 1; pr >>= 1; } (self.op)(vl, vr) } } } } struct Scanner { reader: R, buf_str: Vec, buf_iter: str::SplitWhitespace<'static>, } impl Scanner { fn new(reader: R) -> Self { Self { reader, buf_str: vec![], buf_iter: "".split_whitespace(), } } fn token(&mut self) -> T { loop { if let Some(token) = self.buf_iter.next() { return token.parse().ok().expect("Failed parse"); } self.buf_str.clear(); self.reader .read_until(b'\n', &mut self.buf_str) .expect("Failed read"); self.buf_iter = unsafe { let slice = str::from_utf8_unchecked(&self.buf_str); std::mem::transmute(slice.split_whitespace()) } } } }