#line 1 ".lib/template.hpp" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i>1)|y_bit)) #define bit_kth(i, k) ((i >> k)&1) #define bit_highest(i) (i?63-__builtin_clzll(i):-1) #define bit_lowest(i) (i?__builtin_ctzll(i):-1) #define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t)) using ll = long long; using ld = long double; using ul = uint64_t; using pi = std::pair; using pl = std::pair; using namespace std; template std::ostream &operator<<(std::ostream &dest, const std::pair &p){ dest << p.first << ' ' << p.second; return dest; } template std::ostream &operator<<(std::ostream &dest, const std::vector> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::vector &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::array &v){ if(sz==0) return dest; for(int i=0;i std::ostream &operator<<(std::ostream &dest, const std::set &v){ for(auto itr=v.begin();itr!=v.end();){ dest << *itr; itr++; if(itr!=v.end()) dest << ' '; } return dest; } template std::ostream &operator<<(std::ostream &dest, const std::map &v){ for(auto itr=v.begin();itr!=v.end();){ dest << '(' << itr->first << ", " << itr->second << ')'; itr++; if(itr!=v.end()) dest << '\n'; } return dest; } template vector make_vec(size_t sz, T val){return std::vector(sz, val);} template auto make_vec(size_t sz, Tail ...tail){ return std::vector(tail...))>(sz, make_vec(tail...)); } template vector read_vec(size_t sz){ std::vector v(sz); for(int i=0;i<(int)sz;i++) std::cin >> v[i]; return v; } template auto read_vec(size_t sz, Tail ...tail){ auto v = std::vector(tail...))>(sz); for(int i=0;i<(int)sz;i++) v[i] = read_vec(tail...); return v; } void io_init(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } #line 1 ".lib/data_structure/segment_tree/lazy_segment_tree.hpp" #line 1 ".lib/monoid.hpp" #include #line 8 ".lib/monoid.hpp" struct point_min_range_min{ template static T id(){ return std::numeric_limits::max(); } template static T update(T a, T b){ return std::min(a, b); } template static T merge(T a, T b){ return std::min(a, b); } }; struct point_min_range_second_min{ template static T id(){ return {std::numeric_limits::max(), std::numeric_limits::max()}; } template static T update(T a, T b){ if(a.first <= b.first) return {a.first, std::min(a.second, b.first)}; else return {b.first, std::min(a.first, b.second)}; } template static T merge(T a, T b){ if(a.first <= b.first) return {a.first, std::min(a.second, b.first)}; else return {b.first, std::min(a.first, b.second)}; } }; struct point_max_range_max{ template static T id(){ return std::numeric_limits::min(); } template static T update(T a, T b){ return std::max(a, b); } template static T merge(T a, T b){ return std::max(a, b); } template static T flip(T a){ return a; } }; struct point_max_range_second_max{ template static T id(){ return {std::numeric_limits::min(), std::numeric_limits::min()}; } template static T update(T a, T b){ if(a.first >= b.first) return {a.first, std::min(a.second, b.first)}; else return {b.first, std::min(a.first, b.second)}; } template static T merge(T a, T b){ if(a.first >= b.first) return {a.first, std::min(a.second, b.first)}; else return {b.first, std::min(a.first, b.second)}; } }; struct point_mul_range_mul{ template static T id(){ return 1; } template static T update(T a, T b){ return a * b; } template static T merge(T a, T b){ return a * b; } }; struct point_add_range_min{ template static T id(){ return std::numeric_limits::max(); } template static T update(T a, T b){ if(a == id()) return b; else if(b == id()) return a; return a + b; } template static T merge(T a, T b){ return std::min(a, b); } }; struct point_add_range_max{ template static T id(){ return std::numeric_limits::min(); } template static T update(T a, T b){ if(a == id()) return b; else if(b == id()) return a; return a + b; } template static T merge(T a, T b){ return std::max(a, b); } }; struct point_add_range_sum{ template static T id(){ return 0; } template static T update(T a, T b){ return a + b; } template static T merge(T a, T b){ return a + b; } template static T flip(T a){ return a; } }; struct point_set_range_composite{ static constexpr int mod = 998244353; template static T id(){ return {1, 0}; } template static T update(T a, T b){ return b; } template static T merge(T a, T b){ int xy = ((long long)a.first * b.first) % mod; int ab = ((long long)a.second * b.first + b.second) % mod; return {xy, ab}; } }; struct point_set_range_composite_flip{ static constexpr int mod = 998244353; template static T id(){ return {1, 0, 0}; } template static T update(T a, T b){ return b; } template static T flip(T a){ return {a[0], a[2], a[1]}; } template static T merge(T a, T b){ int xy = ((long long)a[0] * b[0]) % mod; int ab = ((long long)a[1] * b[0] + b[1]) % mod; int ba = ((long long)b[2] * a[0] + a[2]) % mod; return {xy, ab, ba}; } }; struct point_add_range_gcd{ template static Val __binary_gcd(Val a, Val b){ if(!a || !b) return !a ? b : a; if(a < 0) a *= -1; if(b < 0) b *= -1; int shift = __builtin_ctzll(a | b); // [1] gcd(2a', 2b') = 2 * gcd(a', b') a >>= __builtin_ctzll(a); do{ // if b is odd // gcd(2a', b) = gcd(a', b), if a = 2a'(a is even) // gcd(a, b) = gcd(|a - b|, min(a, b)), if a is odd b >>= __builtin_ctzll(b); // make b odd if(a > b) std::swap(a, b); b -= a; }while(b); // gcd(a, 0) = a return a << shift; // [1] } template static Val id(){ return 0; } template static Val update(Val a, Val b){ return a + b; } template static Val merge(Val a, Val b){ return __binary_gcd(a, b); } }; // 区間set, これまでにsetした物の中ならどれかを取得 struct range_set_get_any{ template static Val id1(){ return nullptr; } template static Lazy id2(){ return nullptr; } template static Lazy propagate(Lazy l, Lazy x){ return (x == nullptr ? l : x); } template static Val apply(Val v, Lazy x, int l, int r){ return (x == nullptr ? v : x); } }; struct range_add_range_sum{ template static T id1(){ return T(0); } template static E id2(){ return E(0); } template static T merge(T a, T b){ return a + b; } template static T apply(T a, E b, int l, int r){ return a + b * (r - l); } template static E propagate(E a, E b){ return a + b; } template static T flip(T a){ return a; } }; struct range_max_range_max{ template static T id1(){ return std::numeric_limits::min(); } template static E id2(){ return std::numeric_limits::min(); } template static T merge(T a, T b){ return std::max(a, b); } template static T apply(T a, E b, int l, int r){ return std::max(a, b); } template static E propagate(E a, E b){ return std::max(a, b); } }; struct range_add_range_max{ template static T id1(){ return std::numeric_limits::min(); } template static E id2(){ return 0; } template static T merge(T a, T b){ return std::max(a, b); } template static T apply(T a, E b, int l, int r){ if(a == id1()) return b * (r - l); return a + b; } template static E propagate(E a, E b){ return a + b; } }; struct range_add_range_min{ template static T id1(){ return std::numeric_limits::max(); } template static E id2(){ return 0; } template static T merge(T a, T b){ return std::min(a, b); } template static T apply(T a, E b, int l, int r){ if(a == id1()) return b * (r - l); return a + b; } template static E propagate(E a, E b){ return a + b; } }; struct range_add_range_argmin{ template static T id1(){ return {std::numeric_limits::max(), -1} ; } template static E id2(){ return 0; } template static T merge(T a, T b){ return std::min(a, b); } template static T apply(T a, E b, int l, int r){ if(a == id1()) return a; return {a.first + b, a.second}; } template static E propagate(E a, E b){ return a + b; } }; /* #include struct range_affine_range_sum{ const static long long MOD = 998244353; template static T id1(){ return 0; } template static E id2(){ return E{1, 0}; } template static T merge(T a, T b){ return (a + b) % MOD; } template static T apply(T a, E b, int l, int r){ return (a * b[0] + b[1] * (r - l)) % MOD; } template static E propagate(E a, E b){ return E{(a[0] * b[0]) % MOD, (a[1] * b[0] + b[1]) % MOD}; } }; */ struct range_affine_range_sum{ const static int MOD = 998244353; template static T id1(){ return 0; } template static E id2(){ return E{1, 0}; } template static T merge(T a, T b){ return (a + b) % MOD; } template static T apply(T a, E b, int l, int r){ return ((long long)a * b.first + (long long)b.second * (r - l)) % MOD; } template static E propagate(E a, E b){ return E{((long long)a.first * b.first) % MOD, ((long long)a.second * b.first + b.second) % MOD}; } }; struct range_add_range_min_count{ static constexpr int INF = std::numeric_limits::max(); template static T id1(){ return {INF, 0}; } template static E id2(){ return 0; } template static T merge(T a, T b){ if(a.first != b.first) return a.first < b.first ? a : b; return {a.first, a.second + b.second}; } template static T apply(T a, E b, int l, int r){ if(a.first == INF) return {b, r - l}; return {a.first + b, a.second}; } template static E propagate(E a, E b){ return a + b; } }; struct range_composite_lct{ static constexpr int MOD = 998244353; template // 1x + 0, 1x + 0 static T id1(){ return std::array{1, 0, 0}; } // no use template static E id2(){ return false; } // b(a(x)), a(b(x)) template static T merge(T a, T b){ int ba1 = ((long long)b[0] * a[0]) % MOD; int ba2 = ((long long)b[0] * a[1] + b[1]) % MOD; int ab2 = ((long long)a[0] * b[2] + a[2]) % MOD; return std::array{ba1, ba2, ab2}; } // no use template static T apply(T a, E b, int l, int r){ return a; } // no use template static E propagate(E a, E b){ return false; } // template static T flip(T a){ return std::array{a[0], a[2], a[1]}; } }; #line 8 ".lib/data_structure/segment_tree/lazy_segment_tree.hpp" template struct lazy_segment_tree{ private: int N, M; struct node{ Val sum; Lazy lazy; node(Val val = monoid::template id1()): sum(val), lazy(monoid::template id2()){} }; static constexpr int ceil_pow2(int n){ int m = 1; while(m < n) m <<= 1; return m; } std::vector V; inline void push_down(int k, int l, int r){ if(V[k].lazy == monoid::template id2()) return; int mid = (l + r) >> 1; propagate(k * 2 + 1, l, mid, V[k].lazy); propagate(k * 2 + 2, mid, r, V[k].lazy); V[k].lazy = monoid::template id2(); } inline void propagate(int k, int l, int r, Lazy x){ V[k].sum = monoid::template apply(V[k].sum, x, l, r); V[k].lazy = monoid::template propagate(V[k].lazy, x); } Val set(int a, Val x, int k, int l, int r){ if(r - l == 1) return V[k].sum = x; push_down(k, l, r); int mid = (l + r) >> 1; if(a < mid){ return V[k].sum = monoid::template merge(set(a, x, k * 2 + 1, l, mid), V[k * 2 + 2].sum); }else{ return V[k].sum = monoid::template merge(V[k * 2 + 1].sum, set(a, x, k * 2 + 2, mid, r)); } } Val get(int a, int k, int l, int r){ if(r - l == 1) return V[k].sum; push_down(k, l, r); int mid = (l + r) >> 1; if(a < mid) return get(a, k * 2 + 1, l, mid); else return get(a, k * 2 + 2, mid, r); } Val update(int a, int b, Lazy x, int k, int l, int r){ if(r <= a || b <= l) return V[k].sum; if(a <= l && r <= b){ propagate(k, l, r, x); return V[k].sum; } push_down(k, l, r); int mid = (l + r) >> 1; return V[k].sum = monoid::template merge(update(a, b, x, k * 2 + 1, l, mid), update(a, b, x, k * 2 + 2, mid, r)); } Val query(int a, int b, int k, int l, int r){ if(r <= a || b <= l) return monoid::template id1(); if(a <= l && r <= b) return V[k].sum; push_down(k, l, r); int mid = (l + r) >> 1; return monoid::template merge(query(a, b, k * 2 + 1, l, mid), query(a, b, k * 2 + 2, mid, r)); } template inline std::pair bisect_from_left(int a, const F &f, Val val, int k, int l, int r){ if(r <= a) return {-1, val}; if(k < M - 1) push_down(k, l, r); if(a <= l){ Val merged = monoid::template merge(val, V[k].sum); if(!f(merged)) return {-1, merged}; if(k >= M - 1) return {l, merged}; } int mid = (l + r) >> 1; auto left = bisect_from_left(a, f, val, 2 * k + 1, l, mid); if(left.first != -1) return left; return bisect_from_left(a, f, left.second, 2 * k + 2, mid, r); } template inline std::pair bisect_from_left2(int a, const F &f, Val val, int k, int l, int r){ if(r <= a) return {-1, val}; if(k < M - 1) push_down(k, l, r); if(a <= l){ Val merged = monoid::template merge(val, V[k].sum); if(!f(merged, l, r)) return {-1, merged}; if(k >= M - 1) return {l, merged}; } int mid = (l + r) >> 1; auto left = bisect_from_left2(a, f, val, 2 * k + 1, l, mid); if(left.first != -1) return left; return bisect_from_left2(a, f, left.second, 2 * k + 2, mid, r); } template inline std::pair bisect_from_right(int a, const F &f, Val val, int k, int l, int r){ if(a <= l) return {-1, val}; if(k < M - 1) push_down(k, l, r); if(r <= a){ Val merged = monoid::template merge(val, V[k].sum); if(!f(merged)) return {-1, merged}; if(k >= M - 1) return {l, merged}; } int mid = (l + r) >> 1; auto right = bisect_from_right(a, f, val, 2 * k + 2, mid, r); if(right.first != -1) return right; return bisect_from_right(a, f, right.second, 2 * k + 1, l, mid); } template inline std::pair bisect_from_right2(int a, const F &f, Val val, int k, int l, int r){ if(a <= l) return {-1, val}; if(k < M - 1) push_down(k, l, r); if(r <= a){ Val merged = monoid::template merge(val, V[k].sum); if(!f(merged, l, r)) return {-1, merged}; if(k >= M - 1) return {l, merged}; } int mid = (l + r) >> 1; auto right = bisect_from_right2(a, f, val, 2 * k + 2, mid, r); if(right.first != -1) return right; return bisect_from_right2(a, f, right.second, 2 * k + 1, l, mid); } public: lazy_segment_tree(): N(0), M(0){} lazy_segment_tree(int n): N(n), M(ceil_pow2(N)), V(2 * M - 1, node()){} lazy_segment_tree(const std::vector &v): N(v.size()), M(ceil_pow2(N)), V(2 * M - 1){ for(int i = 0; i < M; i++) V[i + M - 1] = node(i < N ? v[i] : monoid::template id1()); for(int i = M - 2; i >= 0; i--) V[i].sum = monoid::template merge(V[i * 2 + 1].sum, V[i * 2 + 2].sum); } int size(){ return N; } // val[k] <- x Val set(int k, Val x){ return set(k, x, 0, 0, M); } // val[k] Val get(int k){ return get(k, 0, 0, M); } // sum[a, b) Val query(int a, int b){ return query(a, b, 0, 0, M); } Val query_all(){ return V[0].sum; } // apply([a, b), x) Val update(int a, int b, Lazy x){ return update(a, b, x, 0, 0, M); } // f(sum[l, r))が初めてtrueになる // f(sum[l, i)), l <= i < r = false // f(sum[l, j)), r <= j <= n = true // となるような{r, sum[l, r)} 無い場合は r = -1 template std::pair bisect_from_left(int l, const F &f){ return bisect_from_left(l, f, monoid::template id1(), 0, 0, M); } template std::pair bisect_from_left2(int l, const F &f){ return bisect_from_left2(l, f, monoid::template id1(), 0, 0, M); } // f(sum[l, r))が初めてtrueになる // f(sum[i, r)), l < i < r = false // f(sum[j, r)), 0 <= j <= l = true // となるような{l, sum[l, r)} 無い場合は l = -1 template std::pair bisect_from_right(int r, const F &f){ return bisect_from_right(r, f, monoid::template id1(), 0, 0, M); } template std::pair bisect_from_right2(int r, const F &f){ return bisect_from_right2(r, f, monoid::template id1(), 0, 0, M); } }; #line 1 ".lib/data_structure/range_query/accumulate1d.hpp" #line 5 ".lib/data_structure/range_query/accumulate1d.hpp" template struct accumulate1d{ std::vector sum; accumulate1d(){} accumulate1d(const std::vector &v): sum(v){ for(int i = 1; i < v.size(); i++) sum[i] = sum[i - 1] + v[i]; } // [0, r)の和, 範囲外の部分は全て単位元 Val query(int r){ r = std::min(r, (int)sum.size()); if(r <= 0) return 0; return sum[r - 1]; } // [l, r)の和, 範囲外の部分は全て単位元 Val query(int l, int r){ l = std::max(l, 0); r = std::min(r, (int)sum.size()); if(r <= l) return 0; return (l == 0 ? sum[r - 1] : (sum[r - 1] - sum[l - 1])); } // [0, k]がx以上になる最小インデックス, ない場合はn int lower_bound(Val x){ return std::lower_bound(sum.begin(), sum.end(), x) - sum.begin(); } // [0, k]がxより大きくなる最小インデックス, ない場合はn int upper_bound(Val x){ return std::upper_bound(sum.begin(), sum.end(), x) - sum.begin(); } }; #line 4 "a.cpp" int main(){ io_init(); int n, q; std::cin >> n >> q; auto a = read_vec(q, 3); int lim = 100001; lazy_segment_tree seg(lim); range(i, 0, q) seg.update(a[i][1], a[i][2], 1); vector frac(lim, 0); range(i, 0, lim) if(seg.get(i)) frac[i] = 1 / ld(seg.get(i)); accumulate1d ac(frac); vector ans(n, 0); range(i, 0, q) ans[a[i][0] - 1] += ac.query(a[i][1], a[i][2]); range(i, 0, n) std::cout << setprecision(16) << ans[i] << '\n'; }