// #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using lg = long long; using ld = long double; using pii = pair; using pll = pair; #define TEST cerr << "TEST" << endl #define AMARI 998244353 // #define AMARI 1000000007 #define TEMOTO ((sizeof(long double) == 16) ? false : true) #define TIME_LIMIT 1980 * (TEMOTO ? 1 : 1000) #define el '\n' #define El '\n' // 抽象再帰セグ木?(抽象セグ木の定義分からんな)(遅延ではない) // ococo_segtree rsq(n,0);みたいに宣言する template class ococo_segtree { T func(T a, T b) { // ここに演算を入れる return (a + b); } public: int n; T tmax; // range minimum query vector rmq; //(データの大きさ,単位元) ococo_segtree(int N, T t) { syokica(N, t); } // 配列の初期化 O(N) void syokica(int a, T t) { n = 1; tmax = t; while(n < a) n *= 2; rmq.resize(2 * n - 1); for(int i = 0; i < 2 * n - 1; i++) { rmq[i] = tmax; } } // a[i]をxにする O(logN) void update_num(int i, T x) { i += (n - 1); rmq[i] = x; while(i) { i = (i - 1) / 2; rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]); } } // a[i]にxを加える O(logN) void add_num(int i, T x) { i += (n - 1); rmq[i] = func(rmq[i], x); while(i) { i = (i - 1) / 2; rmq[i] = func(rmq[i * 2 + 1], rmq[i * 2 + 2]); } } T get_minimum2(int a, int b, int k, int l, int r) { if(a <= l && r <= b) return rmq[k]; else if(r <= a || b <= l) return tmax; else return func(get_minimum2(a, b, k * 2 + 1, l, (l + r) / 2), get_minimum2(a, b, k * 2 + 2, (l + r) / 2, r)); } //[l,r)の区間演算の取得 O(logN) T get_val(int l, int r) { return get_minimum2(l, r, 0, 0, n); } }; // 区間可算ができる遅延セグ木 // 最小値の取得と、区間和の取得ができる template class ococo_raq_lazy_segtree { public: int n; T tmax; // rsq:Range Sum Query vector rsq, lazy_rsq; // rmq;Range Minimum Query vector rmq, lazy_rmq; ococo_raq_lazy_segtree(int N, T t) { syokica(N, t); } // 配列の初期化 O(N) //(サイズ、指定した型の最大値)を引数にとる // rmqをtmax(指定した型の最大値)で初期化しているが、場合に合わせて初期化する値は変えた方が良いこともある。 void syokica(int a, T t) { n = 1; tmax = t; while(n < a) n *= 2; rsq.resize(2 * n - 1); rmq.resize(2 * n - 1); lazy_rsq.resize(2 * n - 1); lazy_rmq.resize(2 * n - 1); for(int i = 0; i < 2 * n - 1; i++) { rsq[i] = 0; rmq[i] = tmax; lazy_rsq[i] = 0; lazy_rmq[i] = tmax; } } // k番目の点についての遅延評価 O(1) void lazy_evaluate(int k, int l, int r) { if(lazy_rsq[k] != 0) { rsq[k] += lazy_rsq[k]; if(r - l > 1) { lazy_rsq[2 * k + 1] += (lazy_rsq[k] / 2); lazy_rsq[2 * k + 2] += (lazy_rsq[k] / 2); } lazy_rsq[k] = 0; } if(lazy_rmq[k] != tmax) { rmq[k] += lazy_rmq[k]; if(r - l > 1) { if(lazy_rmq[2 * k + 1] == tmax) lazy_rmq[2 * k + 1] = lazy_rmq[k]; else lazy_rmq[2 * k + 1] += lazy_rmq[k]; if(lazy_rmq[2 * k + 2] == tmax) lazy_rmq[2 * k + 2] = lazy_rmq[k]; else lazy_rmq[2 * k + 2] += lazy_rmq[k]; } lazy_rmq[k] = tmax; } } void add_num2(int a, int b, T x, int k, int l, int r) { lazy_evaluate(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b) { lazy_rsq[k] += (T)(r - l) * x; if(lazy_rmq[k] == tmax) lazy_rmq[k] = x; else lazy_rmq[k] += x; lazy_evaluate(k, l, r); } else { add_num2(a, b, x, 2 * k + 1, l, (l + r) / 2); add_num2(a, b, x, 2 * k + 2, (l + r) / 2, r); rsq[k] = rsq[2 * k + 1] + rsq[2 * k + 2]; rmq[k] = min(rmq[2 * k + 1], rmq[2 * k + 2]); } } //[l,r)にxを加える void add_num(int l, int r, T x) { add_num2(l, r, x, 0, 0, n); } T get_sum2(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return 0; lazy_evaluate(k, l, r); if(a <= l && r <= b) return rsq[k]; else { return (get_sum2(a, b, k * 2 + 1, l, (l + r) / 2) + get_sum2(a, b, k * 2 + 2, (l + r) / 2, r)); } } //[l,r)の和の取得 O(logN) T get_sum(int l, int r) { return get_sum2(l, r, 0, 0, n); } T get_minimum2(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return tmax; lazy_evaluate(k, l, r); if(a <= l && r <= b) return rmq[k]; else return min(get_minimum2(a, b, k * 2 + 1, l, (l + r) / 2), get_minimum2(a, b, k * 2 + 2, (l + r) / 2, r)); } //[l,r)の最小値の取得 O(logN) T get_minimum(int l, int r) { return get_minimum2(l, r, 0, 0, n); } }; #define MULTI_TEST_CASE false void solve(void) { int n,q; cin >> n >> q; vector> ensou(n); ococo_raq_lazy_segtree ilos(1e5+1,0); while(q--){ int i,s,t; cin >> i >> s >> t; i--; ensou[i].push_back(pair(s,t)); ilos.add_num(s,t,1); //cerr << s << t << el; //cerr << ilos.get_sum(s,s + 1) << el; } ococo_segtree dos(1e5+1,0); for(int i = 0; i < 1e5; i++){ dos.add_num(i,1 / (ld)ilos.get_sum(i,i+1)); //if(i == 0)cerr << ilos.get_minimum(0,1); } vector ans(n); cout << fixed << setprecision(15); for(int i = 0; i < n; i++){ for(int j = 0; j < ensou[i].size(); j++){ ans[i] += dos.get_val(ensou[i][j].first,ensou[i][j].second); } cout << ans[i] << el; } return; } void calc(void) { return; } int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); calc(); int t = 1; if(MULTI_TEST_CASE) cin >> t; while(t--) { solve(); } return 0; }