#916348 (C++17) No.880 Yet Another Segment Tree Problem

提出ソース
結果

問題	No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー	tonegawa
提出日時	2023-09-28 21:01:39
言語	C++17 (gcc 13.3.0 + boost 1.89.0)
結果	TLE
実行時間	-
コード長	14,429 bytes
記録
コンパイル時間	1,567 ms
コンパイル使用メモリ	144,488 KB
最終ジャッジ日時	2025-02-17 02:50:13
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 32 TLE * 1 -- * 4
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  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 2 "a.cpp"

template<typename beats_struct>
struct segment_tree_beats{
  using Val = typename beats_struct::Val;
  using Lazy = typename beats_struct::Lazy;
  int N, M;
  std::vector<Val> val;
  std::vector<Lazy> lazy;
  std::vector<bool> is_id;

  void push_down(int k, int l, int r){
    if(M - 1 <= k || is_id[k]) return;
    int mid = (l + r) >> 1;
    propagate(k * 2 + 1, l, mid, lazy[k]);
    propagate(k * 2 + 2, mid, r, lazy[k]);
    is_id[k] = true;
  }
  void propagate(int k, int l, int r, const Lazy &x){
    if(k < M - 1){
      if(is_id[k]){
        lazy[k] = x;
        is_id[k] = false;
      }else{
        beats_struct::propagate_lazy(lazy[k], x);
      }
    }
    beats_struct::apply(val[k], x, l, r);
  }
  void set(int a, Val x, int k, int l, int r){
    if(r - l == 1){
      val[k] = x;
      return;
    }
    push_down(k, l, r);
    int mid = (l + r) >> 1;
    if(a < mid) set(a, x, k * 2 + 1, l, mid);
    else set(a, x, k * 2 + 2, mid, r);
    beats_struct::merge_val(val[k], val[k * 2 + 1], val[k * 2 + 2]);
  }
  void get(int a, int k, int l, int r, Val &ans){
    if(r - l == 1){
      ans = val[k];
      return;
    }
    push_down(k, l, r);
    int mid = (l + r) >> 1;
    if(a < mid) get(a, k * 2 + 1, l, mid, ans);
    else get(a, k * 2 + 2, mid, r, ans);
  }
  template<int id>
  void update(int a, int b, const Lazy &x, int k, int l, int r){
    if(r <= a || b <= l || beats_struct::template break_check<id>(val[k], x)) return;
    /*
    if(a <= l && r <= b && beats_struct::template tag_check<id>(val[k], x)){
      propagate(k, l, r, x);
      return;
    }
    */
    if(a <= l && r <= b && beats_struct::template tag_check<id>(val[k], x)){
      if(id == 0){
        propagate(k, l, r, x);
      }else{
        Lazy y(std::gcd(val[k].unique, x.setx));
        propagate(k, l, r, y);
      }
      return;
    }
    push_down(k, l, r);
    update<id>(a, b, x, k * 2 + 1, l, (l + r) / 2);
    update<id>(a, b, x, k * 2 + 2, (l + r) / 2, r);
    beats_struct::merge_val(val[k], val[k * 2 + 1], val[k * 2 + 2]);
  }
  void query(int a, int b, int k, int l, int r, Val &ans){
    if(r <= a || b <= l) return;
    if(a <= l && r <= b){
      Val tmp = beats_struct::id_val();
      beats_struct::merge_val(tmp, ans, val[k]);
      ans = tmp;
      return;
    }
    push_down(k, l, r);
    query(a, b, k * 2 + 1, l, (l + r) / 2, ans);
    query(a, b, k * 2 + 2, (l + r) / 2, r, ans);
  }
  int c2(int x){
    int y = 1;
    while(y < x) y <<= 1;
    return y;
  }
  segment_tree_beats(): N(0), M(0){}
  template<typename T>
  segment_tree_beats(const std::vector<T> &v): N(v.size()), M(c2(N)), val(2 * M - 1, Val()), lazy(M - 1, Lazy()), is_id(M - 1, true){
    for(int i = 0; i < N; i++) val[M - 1 + i] = Val(v[i]);
    for(int i = N; i < M; i++) val[M - 1 + i] = beats_struct::id_val();
    for(int i = M - 2; i >= 0; i--) beats_struct::merge_val(val[i], val[i * 2 + 1], val[i * 2 + 2]);
  }
  template<int id>
  void update(int l, int r, Lazy x){
    update<id>(l, r, x, 0, 0, M);
  }
  Val query(int l, int r){
    Val ans = beats_struct::id_val();
    query(l, r, 0, 0, M, ans);
    return ans;
  }
};

template<typename T>
struct add_chmin_chmax{
  static constexpr T inf = std::numeric_limits<T>::max();
  static constexpr T minf = std::numeric_limits<T>::min();
  struct Val{
    T min, second_min, max, second_max, sum;
    int min_cnt, max_cnt;
    Val(): min(inf), second_min(inf), max(minf), second_max(minf), sum(0), min_cnt(0), max_cnt(0){}
    Val(T x): min(x), second_min(inf), max(x), second_max(minf), sum(x), min_cnt(1), max_cnt(1){}
  };
  struct Lazy{
    T add, lower, upper;
    Lazy(): add(0), lower(minf), upper(inf){}
    Lazy(T a, T b, T c): add(a), lower(b), upper(c){}
  };
  static Val id_val(){
    return Val();
  }
  // l, rをマージしてvに代入
  static void merge_val(Val &v, const Val &l, const Val &r){
    v.sum = l.sum + r.sum;
    if(l.max == r.max){
      v.max = l.max;
      v.max_cnt = l.max_cnt + r.max_cnt;
      v.second_max = std::max(l.second_max, r.second_max);
    }else if(l.max > r.max){
      v.max = l.max;
      v.max_cnt = l.max_cnt;
      v.second_max = std::max(l.second_max, r.max);
    }else{
      v.max = r.max;
      v.max_cnt = r.max_cnt;
      v.second_max = std::max(l.max, r.second_max);
    }
    if(l.min == r.min){
      v.min = l.min;
      v.min_cnt = l.min_cnt + r.min_cnt;
      v.second_min = std::min(l.second_min, r.second_min);
    }else if(l.min < r.min){
      v.min = l.min;
      v.min_cnt = l.min_cnt;
      v.second_min = std::min(l.second_min, r.min);
    }else{
      v.min = r.min;
      v.min_cnt = r.min_cnt;
      v.second_min = std::min(l.min, r.second_min);
    }
  }
  static void apply(Val &a, const Lazy &b, int l, int r){
    if(b.add){
      a.min += b.add;
      if(a.second_min != inf) a.second_min += b.add;
      a.max += b.add;
      if(a.second_max != minf) a.second_max += b.add;
      a.sum += b.add * (r - l);
    }
    if(a.min < b.lower){
      a.sum += (b.lower - a.min) * a.min_cnt;
      if(a.second_max == a.min) a.second_max = b.lower;
      else if(a.max == a.min) a.max = b.lower, a.second_max = minf;
      a.min = b.lower;
    }
    if(b.upper < a.max){
      a.sum -= (a.max - b.upper) * a.max_cnt;
      if(a.second_min == a.max) a.second_min = b.upper;
      else if(a.min == a.max) a.min = b.upper, a.second_min = inf;
      a.max = b.upper;
    }
  }
  static void propagate_lazy(Lazy &a, const Lazy &b){
    if(b.add){
      a.add += b.add;
      if(a.lower != minf) a.lower += b.add;
      if(a.upper != inf) a.upper += b.add;
    }
    if(a.upper <= b.lower) a.lower = a.upper = b.lower;
    else if(b.upper <= a.lower) a.lower = a.upper = b.upper;
    else{
      a.lower = std::max(a.lower, b.lower);
      a.upper = std::min(a.upper, b.upper);
    }
  }
  // chmin
  template<int id, std::enable_if_t<id == 0>* = nullptr>
  static bool break_check(const Val &v, const Lazy &x){
    return v.max < x.upper;
  }
  template<int id, std::enable_if_t<id == 0>* = nullptr>
  static bool tag_check(const Val &v, const Lazy &x){
    return v.second_max < x.upper;
  }
  // chmax
  template<int id, std::enable_if_t<id == 1>* = nullptr>
  static bool break_check(const Val &v, const Lazy &x){
    return v.min > x.lower;
  }
  template<int id, std::enable_if_t<id == 1>* = nullptr>
  static bool tag_check(const Val &v, const Lazy &x){
    return v.second_min > x.lower;
  }
  // add
  template<int id, std::enable_if_t<id == 2>* = nullptr>
  static bool break_check(const Val &v, const Lazy &x){
    return false;
  }
  template<int id, std::enable_if_t<id == 2>* = nullptr>
  static bool tag_check(const Val &v, const Lazy &x){
    return true;
  }
};


template<typename T>
struct abc256ex_set_div_sum{
  static constexpr T minf = std::numeric_limits<T>::min();
  struct Val{
    T sum, unique; // unique != minfなら区間がその値でユニーク
    Val(): sum(0), unique(minf){}
    Val(T x): sum(x), unique(x){}
  };
  struct Lazy{
    T setx; 
    Lazy(): setx(minf){}
    Lazy(T x): setx(x){}
    /* update関数を書き換える
    if(a <= l && r <= b && beats_struct::template tag_check<id>(val[k], x)){
      if(id == 0){
        propagate(k, l, r, x);
      }else{
        Lazy y(val[k].unique / x.setx);
        propagate(k, l, r, y);
      }
      return;
    }
    */
  };
  static Val id_val(){
    return Val();
  }
  // l, rをマージしてvに代入
  static void merge_val(Val &v, const Val &l, const Val &r){
    v.sum = l.sum + r.sum;
    if(l.unique == r.unique) v.unique = l.unique;
    else v.unique = minf;
  }
  static void apply(Val &a, const Lazy &b, int l, int r){
    a.sum = b.setx * (r - l);
    a.unique = b.setx;
  }
  static void propagate_lazy(Lazy &a, const Lazy &b){
    a = b;
  }
  // set
  template<int id, std::enable_if_t<id == 0>* = nullptr>
  static bool break_check(const Val &v, const Lazy &x){
    return false;
  }
  template<int id, std::enable_if_t<id == 0>* = nullptr>
  static bool tag_check(const Val &v, const Lazy &x){
    return true;
  }
  // div
  template<int id, std::enable_if_t<id == 1>* = nullptr>
  static bool break_check(const Val &v, const Lazy &x){
    return v.unique == 0;
  }
  template<int id, std::enable_if_t<id == 1>* = nullptr>
  static bool tag_check(const Val &v, const Lazy &x){
    return v.unique != minf;
  }
};


template<typename T>
struct yuki880_set_gcd_min_sum{
  static constexpr T minf = std::numeric_limits<T>::min();
  struct Val{
    T sum, unique, max;
    Val(): sum(0), unique(minf), max(minf){}
    Val(T x): sum(x), unique(x), max(x){}
  };
  struct Lazy{
    T setx; 
    Lazy(): setx(minf){}
    Lazy(T x): setx(x){}
    /* update関数を書き換える
    if(a <= l && r <= b && beats_struct::template tag_check<id>(val[k], x)){
      if(id == 0){
        propagate(k, l, r, x);
      }else{
        Lazy y(gcd(val[k].unique, x.setx));
        propagate(k, l, r, y);
      }
      return;
    }
    */
  };
  static Val id_val(){
    return Val();
  }
  // l, rをマージしてvに代入
  static void merge_val(Val &v, const Val &l, const Val &r){
    v.sum = l.sum + r.sum;
    v.max = std::max(l.max, r.max);
    if(l.unique == r.unique) v.unique = l.unique;
    else v.unique = minf;
  }
  static void apply(Val &a, const Lazy &b, int l, int r){
    a.sum = b.setx * (r - l);
    a.max = b.setx;
    a.unique = b.setx;
  }
  static void propagate_lazy(Lazy &a, const Lazy &b){
    a = b;
  }
  // set
  template<int id, std::enable_if_t<id == 0>* = nullptr>
  static bool break_check(const Val &v, const Lazy &x){
    return false;
  }
  template<int id, std::enable_if_t<id == 0>* = nullptr>
  static bool tag_check(const Val &v, const Lazy &x){
    return true;
  }
  // gcd
  template<int id, std::enable_if_t<id == 1>* = nullptr>
  static bool break_check(const Val &v, const Lazy &x){
    return v.unique != minf && std::gcd(v.unique, x.setx) == v.unique;
  }
  template<int id, std::enable_if_t<id == 1>* = nullptr>
  static bool tag_check(const Val &v, const Lazy &x){
    return v.unique != minf;
  }
};





int main(){
  io_init();
  int n, q;
  std::cin >> n >> q;
  auto a = read_vec<ll>(n);
  segment_tree_beats<yuki880_set_gcd_min_sum<ll>> seg(a);

  for(int i = 0; i < q; i++){
    long long x, y, z, v;
    std::cin >> x >> y >> z;
    y--;
    if(x == 3){
      std::cout << seg.query(y, z).max << '\n';
    }else if(x == 4){
      std::cout << seg.query(y, z).sum << '\n';
    }else{
      std::cin >> v;
      if(x == 1){
        seg.update<0>(y, z, {v});
      }else if(x == 2){
        seg.update<1>(y, z, {v});
      }
    }
  }
}
yukicoder

結果

ソースコード
