結果

問題 No.2462 七人カノン
コンテスト
ユーザー tonegawa
提出日時 2023-09-08 21:42:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 21,462 bytes
コンパイル時間 1,495 ms
コンパイル使用メモリ 141,148 KB
最終ジャッジ日時 2025-02-16 19:42:46
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 ".lib/template.hpp"


#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>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<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(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 <limits>
#line 8 ".lib/monoid.hpp"

struct point_min_range_min{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::max();
  }
  template<typename T>
  static T update(T a, T b){
    return std::min(a, b);
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
};
struct point_min_range_second_min{
  template<typename T>
  static T id(){
    return {std::numeric_limits<long long>::max(), std::numeric_limits<long long>::max()};
  }
  template<typename T>
  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<typename T>
  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<typename T>
  static T id(){
    return std::numeric_limits<T>::min();
  }
  template<typename T>
  static T update(T a, T b){
    return std::max(a, b);
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
  template<typename T>
  static T flip(T a){
    return a;
  }
};
struct point_max_range_second_max{
  template<typename T>
  static T id(){
    return {std::numeric_limits<long long>::min(), std::numeric_limits<long long>::min()};
  }
  template<typename T>
  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<typename T>
  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<typename T>
  static T id(){
    return 1;
  }
  template<typename T>
  static T update(T a, T b){
    return a * b;
  }
  template<typename T>
  static T merge(T a, T b){
    return a * b;
  }
};
struct point_add_range_min{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::max();
  }
  template<typename T>
  static T update(T a, T b){
    if(a == id<T>()) return b;
    else if(b == id<T>()) return a;
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
};

struct point_add_range_max{
  template<typename T>
  static T id(){
    return std::numeric_limits<T>::min();
  }
  template<typename T>
  static T update(T a, T b){
    if(a == id<T>()) return b;
    else if(b == id<T>()) return a;
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
};

struct point_add_range_sum{
  template<typename T>
  static T id(){
    return 0;
  }
  template<typename T>
  static T update(T a, T b){
    return a + b;
  }
  template<typename T>
  static T merge(T a, T b){
    return a + b;
  }
  template<typename T>
  static T flip(T a){
    return a;
  }
};
struct point_set_range_composite{
  static constexpr int mod = 998244353;
  template<typename T>
  static T id(){
    return {1, 0};
  }
  template<typename T>
  static T update(T a, T b){
    return b;
  }
  template<typename T>
  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<typename T>
  static T id(){
    return {1, 0, 0};
  }
  template<typename T>
  static T update(T a, T b){
    return b;
  }
  template<typename T>
  static T flip(T a){
    return {a[0], a[2], a[1]};
  }
  template<typename T>
  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<typename Val>
  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<typename Val>
  static Val id(){
    return 0;
  }
  template<typename Val>
  static Val update(Val a, Val b){
    return a + b;
  }
  template<typename Val>
  static Val merge(Val a, Val b){
    return __binary_gcd(a, b);
  }
};
// 区間set, これまでにsetした物の中ならどれかを取得
struct range_set_get_any{
  template<typename Val>
  static Val id1(){
    return nullptr;
  }
  template<typename Lazy>
  static Lazy id2(){
    return nullptr;
  }
  template<typename Lazy>
  static Lazy propagate(Lazy l, Lazy x){
    return (x == nullptr ? l : x);
  }
  template<typename Val, typename Lazy>
  static Val apply(Val v, Lazy x, int l, int r){
    return (x == nullptr ? v : x);
  }
};

struct range_add_range_sum{
  template<typename T>
  static T id1(){
    return T(0);
  }
  template<typename E>
  static E id2(){
    return E(0);
  }
  template<typename T>
  static T merge(T a, T b){
    return a + b;
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return a + b * (r - l);
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
  template<typename T>
  static T flip(T a){
    return a;
  }
};

struct range_max_range_max{
  template<typename T>
  static T id1(){
    return std::numeric_limits<T>::min();
  }
  template<typename E>
  static E id2(){
    return std::numeric_limits<E>::min();
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return std::max(a, b);
  }
  template<typename E>
  static E propagate(E a, E b){
    return std::max(a, b);
  }
};
struct range_add_range_max{
  template<typename T>
  static T id1(){
    return std::numeric_limits<T>::min();
  }
  template<typename E>
  static E id2(){
    return 0;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::max(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    if(a == id1<T>()) return b * (r - l);
    return a + b;
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

struct range_add_range_min{
  template<typename T>
  static T id1(){
    return std::numeric_limits<T>::max();
  }
  template<typename E>
  static E id2(){
    return 0;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    if(a == id1<T>()) return b * (r - l);
    return a + b;
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

struct range_add_range_argmin{
  template<typename T>
  static T id1(){
    return {std::numeric_limits<long long>::max(), -1} ;
  }
  template<typename E>
  static E id2(){
    return 0;
  }
  template<typename T>
  static T merge(T a, T b){
    return std::min(a, b);
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    if(a == id1<T>()) return a;
    return {a.first + b, a.second};
  }
  template<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

/*
#include <array>
struct range_affine_range_sum{
  const static long long MOD = 998244353;
  template<typename T>
  static T id1(){
    return 0;
  }
  template<typename E>
  static E id2(){
    return E{1, 0};
  }
  template<typename T>
  static T merge(T a, T b){
    return (a + b) % MOD;
  }
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return (a * b[0] + b[1] * (r - l)) % MOD;
  }
  template<typename E>
  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<typename T>
  static T id1(){
    return 0;
  }
  template<typename E>
  static E id2(){
    return E{1, 0};
  }
  template<typename T>
  static T merge(T a, T b){
    return (a + b) % MOD;
  }
  template<typename T, typename E>
  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<typename E>
  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<int>::max();
  template<typename T>
  static T id1(){
    return {INF, 0};
  }
  template<typename E>
  static E id2(){
    return 0;
  }
  template<typename T>
  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<typename T, typename E>
  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<typename E>
  static E propagate(E a, E b){
    return a + b;
  }
};

struct range_composite_lct{
  static constexpr int MOD = 998244353;
  template<typename T>
  // 1x + 0, 1x + 0
  static T id1(){
    return std::array<int, 3>{1, 0, 0};
  }
  // no use
  template<typename E>
  static E id2(){
    return false;
  }
  // b(a(x)), a(b(x))
  template<typename T>
  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<int, 3>{ba1, ba2, ab2};
  }
  // no use
  template<typename T, typename E>
  static T apply(T a, E b, int l, int r){
    return a;
  }
  // no use
  template<typename E>
  static E propagate(E a, E b){
    return false;
  }
  //
  template<typename T>
  static T flip(T a){
    return std::array<int, 3>{a[0], a[2], a[1]};
  }
};

#line 8 ".lib/data_structure/segment_tree/lazy_segment_tree.hpp"

template<typename monoid, typename Val, typename Lazy>
struct lazy_segment_tree{
private:
  int N, M;
  struct node{
    Val sum;
    Lazy lazy;
    node(Val val = monoid::template id1<Val>()): sum(val), lazy(monoid::template id2<Lazy>()){}
  };
  static constexpr int ceil_pow2(int n){
    int m = 1;
    while(m < n) m <<= 1;
    return m;
  }
  std::vector<node> V;
  inline void push_down(int k, int l, int r){
    if(V[k].lazy == monoid::template id2<Lazy>()) 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<Lazy>();
  }
  inline void propagate(int k, int l, int r, Lazy x){
    V[k].sum = monoid::template apply<Val, Lazy>(V[k].sum, x, l, r);
    V[k].lazy = monoid::template propagate<Lazy>(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<Val>(set(a, x, k * 2 + 1, l, mid), V[k * 2 + 2].sum);
    }else{
      return V[k].sum = monoid::template merge<Val>(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<Val>(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<Val>();
    if(a <= l && r <= b) return V[k].sum;
    push_down(k, l, r);
    int mid = (l + r) >> 1;
    return monoid::template merge<Val>(query(a, b, k * 2 + 1, l, mid), query(a, b, k * 2 + 2, mid, r));
  }
  template<typename F>
  inline std::pair<int, Val> 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>(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<typename F>
  inline std::pair<int, Val> 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>(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<typename F>
  inline std::pair<int, Val> 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>(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<typename F>
  inline std::pair<int, Val> 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>(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<Val> &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<Val>());
    for(int i = M - 2; i >= 0; i--) V[i].sum = monoid::template merge<Val>(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<typename F>
  std::pair<int, Val> bisect_from_left(int l, const F &f){
    return bisect_from_left(l, f, monoid::template id1<Val>(), 0, 0, M);
  }
  template<typename F>
  std::pair<int, Val> bisect_from_left2(int l, const F &f){
    return bisect_from_left2(l, f, monoid::template id1<Val>(), 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<typename F>
  std::pair<int, Val> bisect_from_right(int r, const F &f){
    return bisect_from_right(r, f, monoid::template id1<Val>(), 0, 0, M);
  }
  template<typename F>
  std::pair<int, Val> bisect_from_right2(int r, const F &f){
    return bisect_from_right2(r, f, monoid::template id1<Val>(), 0, 0, M);
  }
};

#line 1 ".lib/data_structure/range_query/accumulate1d.hpp"


#line 5 ".lib/data_structure/range_query/accumulate1d.hpp"

template<typename Val>
struct accumulate1d{
  std::vector<Val> sum;
  accumulate1d(){}
  accumulate1d(const std::vector<Val> &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<int>(q, 3);
  int lim = 100001;
  lazy_segment_tree<range_add_range_sum, ll, ll> seg(lim);
  range(i, 0, q) seg.update(a[i][1], a[i][2], 1);
  vector<ld> frac(lim, 0);
  range(i, 0, lim) if(seg.get(i)) frac[i] = 1 / ld(seg.get(i));
  accumulate1d<ld> ac(frac);
  vector<ld> 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';
}
0