結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー hos.lyric
提出日時 2021-07-25 18:09:28
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 6,564 bytes
記録
コンパイル時間 1,261 ms
コンパイル使用メモリ 64,892 KB
実行使用メモリ 19,200 KB
最終ジャッジ日時 2024-07-21 02:32:30
合計ジャッジ時間 9,674 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 7 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <assert.h>
#include <vector>

using std::vector;

// TODO
template <class T> struct SegmentTreeRec {
  int logN, n;
  vector<T> ts;
  SegmentTreeRec() {}
  explicit SegmentTreeRec(int n_) {
    for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
    ts.resize(n << 1);
  }
  template <class S> explicit SegmentTreeRec(const vector<S> &ss) {
    const int n_ = ss.size();
    for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
    ts.resize(n << 1);
    for (int i = 0; i < n_; ++i) at(i) = T(ss[i]);
    build();
  }
  T &at(int i) {
    return ts[n + i];
  }
  void build() {
    for (int u = n; --u; ) merge(u);
  }

  inline void push(int u) {
    ts[u].push(ts[u << 1], ts[u << 1 | 1]);
  }
  inline void merge(int u) {
    ts[u].merge(ts[u << 1], ts[u << 1 | 1]);
  }

  template <class F, class... Args> void chRec(int u, F f, const Args &... args) {
    if ((ts[u].*f)(args...)) return;
    push(u);
    chRec(u << 1, f, args...);
    chRec(u << 1 | 1, f, args...);
    merge(u);
  }
  template <class F, class... Args> void ch(int a, int b, F f, const Args &... args) {
    assert(0 <= a); assert(a <= b); assert(b <= n);
    if (a == b) return;
    a += n;
    b += n;
    for (int h = logN; h; --h) {
      const int aa = a >> h, bb = b >> h;
      if ((aa << h) != a) push(aa);
      if ((bb << h) != b && aa != bb) push(bb);
    }
    for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
      if (aa & 1) chRec(aa++, f, args...);
      if (bb & 1) chRec(--bb, f, args...);
    }
    for (int h = 1; h <= logN; ++h) {
      const int aa = a >> h, bb = b >> h;
      if ((aa << h) != a) merge(aa);
      if ((bb << h) != b && aa != bb) merge(bb);
    }
  }

  template <class Op, class E, class F, class... Args> auto get(int a, int b, Op op, E e, F f, const Args &... args) {
    assert(0 <= a); assert(a <= b); assert(b <= n);
    if (a == b) return e();
    a += n;
    b += n;
    for (int h = logN; h; --h) {
      const int aa = a >> h, bb = b >> h;
      if ((aa << h) != a) push(aa);
      if ((bb << h) != b && aa != bb) push(bb);
    }
    auto prodL = e(), prodR = e();
    for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
      if (aa & 1) prodL = op(prodL, (ts[aa++].*f)(args...));
      if (bb & 1) prodR = op((ts[--bb].*f)(args...), prodR);
    }
    return op(prodL, prodR);
  }
};

////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <algorithm>

namespace yukicoder880 {

// https://yukicoder.me/problems/no/880
// update range  a[i] <- x
// update range  a[i] <- gcd(a[i], x)
// get  max a[l, r)
// get  sum a[l, r)

using std::__gcd;
using std::max;
using std::min;

constexpr long long INF = 1001001001;

struct Node {
  long long lcm, mx, sz, sum;
  long long lz;
  Node() : lcm(1), mx(0), sz(0), sum(0), lz(-1) {}
  Node(long long val) : lcm(val), mx(val), sz(1), sum(val), lz(-1) {}
  void push(Node &l, Node &r) {
    if (lz != -1) {
      l.set(lz);
      r.set(lz);
      lz = -1;
    }
  }
  void merge(const Node &l, const Node &r) {
    lcm = min(l.lcm / __gcd(l.lcm, r.lcm) * r.lcm, INF);
    mx = max(l.mx, r.mx);
    sz = l.sz + r.sz;
    sum = l.sum + r.sum;
  }
  bool set(long long val) {
    lcm = val;
    mx = val;
    sum = sz * val;
    lz = val;
    return true;
  }
  bool chgcd(long long val) {
    if (sz == 1) {
      lcm = mx = sum = __gcd(lcm, val);
      return true;
    } else if (val % lcm == 0) {
      return true;
    } else {
      return false;
    }
  }
  long long getMax() const {
    return mx;
  }
  long long getSum() const {
    return sum;
  }
};

long long opMax(long long l, long long r) { return max(l, r); }
long long eMax() { return 0; }
long long opSum(long long l, long long r) { return l + r; }
long long eSum() { return 0; }

void unittest() {
  {
    const vector<long long> as{1, 6, 8, 7, 3};
    SegmentTreeRec<Node> seg(as);
    assert(seg.get(0, 5, &opMax, &eMax, &Node::getMax) == 8);
    assert(seg.get(0, 5, &opSum, &eSum, &Node::getSum) == 25);
    seg.ch(0, 5, &Node::chgcd, 6);
    assert(seg.get(0, 5, &opMax, &eMax, &Node::getMax) == 6);
    assert(seg.get(1, 4, &opSum, &eSum, &Node::getSum) == 9);
    seg.ch(0, 5, &Node::set, 10);
    assert(seg.get(0, 4, &opMax, &eMax, &Node::getMax) == 10);
    assert(seg.get(2, 5, &opSum, &eSum, &Node::getSum) == 30);
    seg.ch(2, 4, &Node::chgcd, 3);
    assert(seg.get(1, 3, &opMax, &eMax, &Node::getMax) == 10);
    assert(seg.get(3, 5, &opSum, &eSum, &Node::getSum) == 11);
  }
}

void brute() {
  int N, Q;
  for (; ~scanf("%d%d", &N, &Q); ) {
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld", &A[i]);
    }
    for (int q = 0; q < Q; ++q) {
      int typ, l, r;
      scanf("%d%d%d", &typ, &l, &r);
      --l;
      switch (typ) {
        case 1: {
          long long x;
          scanf("%lld", &x);
          for (int i = l; i < r; ++i) A[i] = x;
        } break;
        case 2: {
          long long x;
          scanf("%lld", &x);
          for (int i = l; i < r; ++i) A[i] = __gcd(A[i], x);
        } break;
        case 3: {
          long long mx = 0;
          for (int i = l; i < r; ++i) if (mx < A[i]) mx = A[i];
          printf("%lld\n", mx);
        } break;
        case 4: {
          long long sum = 0;
          for (int i = l; i < r; ++i) sum += A[i];
          printf("%lld\n", sum);
        } break;
        default: assert(false);
      }
    }
  }
}

void solve() {
  int N, Q;
  for (; ~scanf("%d%d", &N, &Q); ) {
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
      scanf("%lld", &A[i]);
    }
    SegmentTreeRec<Node> seg(A);
    for (int q = 0; q < Q; ++q) {
      int typ, l, r;
      scanf("%d%d%d", &typ, &l, &r);
      --l;
      switch (typ) {
        case 1: {
          long long x;
          scanf("%lld", &x);
          seg.ch(l, r, &Node::set, x);
        } break;
        case 2: {
          long long x;
          scanf("%lld", &x);
          seg.ch(l, r, &Node::chgcd, x);
        } break;
        case 3: {
          const long long res = seg.get(l, r, &opMax, &eMax, &Node::getMax);
          printf("%lld\n", res);
        } break;
        case 4: {
          const long long res = seg.get(l, r, &opSum, &eSum, &Node::getSum);
          printf("%lld\n", res);
        } break;
        default: assert(false);
      }
    }
  }
}

}  // namespace yukicoder880

////////////////////////////////////////////////////////////////////////////////

int main() {
  // yukicoder880::unittest();
  // yukicoder880::brute();
  yukicoder880::solve();
  return 0;
}
0