結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー ei1333333
提出日時 2019-09-06 23:26:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 710 ms / 5,000 ms
コード長 3,468 bytes
コンパイル時間 2,498 ms
コンパイル使用メモリ 202,236 KB
実行使用メモリ 13,440 KB
最終ジャッジ日時 2025-06-20 10:28:14
合計ジャッジ時間 15,482 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 inf = 1LL << 60;

struct Ushitapunichiakun {
  int sz;
  vector< int64 > lazy;
  vector< int64 > latte, malta, sum;

  vector< int64 > lcm;

  Ushitapunichiakun(int N) {
    sz = 1;
    while(sz < N) sz *= 2;
    lazy.assign(2 * sz - 1, inf);
    latte.assign(2 * sz - 1, -inf);
    malta.assign(2 * sz - 1, inf);
    sum.assign(2 * sz - 1, 0);
    lcm.assign(2 * sz - 1, 1);
  }

  void push(int k, int len) {
    if(lazy[k] == inf) return;
    if(k < sz - 1) {
      lazy[2 * k + 1] = lazy[k];
      lazy[2 * k + 2] = lazy[k];
    }
    latte[k] = lazy[k];
    malta[k] = lazy[k];
    sum[k] = lazy[k] * len;
    lcm[k] = lazy[k];
    lazy[k] = inf;
  }

  void update(int k) {
    latte[k] = max(latte[2 * k + 1], latte[2 * k + 2]);
    malta[k] = min(malta[2 * k + 1], malta[2 * k + 2]);
    sum[k] = sum[2 * k + 1] + sum[2 * k + 2];
    if(lcm[2 * k + 1] >= inf || lcm[2 * k + 2] >= inf) lcm[k] = inf;
    else lcm[k] = lcm[2 * k + 1] / __gcd(lcm[2 * k + 1], lcm[2 * k + 2]) * lcm[2 * k + 2];
  }

  void ushi(int a, int b, int64 x, int k, int l, int r) {
    push(k, r - l);
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) {
      lazy[k] = x;
      push(k, r - l);
      return;
    }
    ushi(a, b, x, 2 * k + 1, l, (l + r) / 2);
    ushi(a, b, x, 2 * k + 2, (l + r) / 2, r);
    update(k);
  }

  void ushi(int a, int b, int64 x) {
    ushi(a, b, x, 0, 0, sz);
  }

  int64 sum_query(int a, int b, int k, int l, int r) {
    push(k, r - l);
    if(r <= a || b <= l) return 0;
    if(a <= l && r <= b) return sum[k];
    return sum_query(a, b, 2 * k + 1, l, (l + r) / 2) +
           sum_query(a, b, 2 * k + 2, (l + r) / 2, r);
  }

  int64 sum_query(int a, int b) {
    return sum_query(a, b, 0, 0, sz);
  }

  int64 max_query(int a, int b, int k, int l, int r) {
    push(k, r - l);
    if(r <= a || b <= l) return -inf;
    if(a <= l && r <= b) return latte[k];
    return max(max_query(a, b, 2 * k + 1, l, (l + r) / 2),
               max_query(a, b, 2 * k + 2, (l + r) / 2, r));
  }

  int64 max_query(int a, int b) {
    return max_query(a, b, 0, 0, sz);
  }


  void tapu(int a, int b, int64 x, int k, int l, int r) {
    push(k, r - l);
    if(r <= a || b <= l || x % lcm[k] == 0) return;
    if(a <= l && r <= b && latte[k] == malta[k]) {
      lazy[k] = __gcd(latte[k], x);
      push(k, r - l);
      return;
    }
    tapu(a, b, x, 2 * k + 1, l, (l + r) / 2);
    tapu(a, b, x, 2 * k + 2, (l + r) / 2, r);
    update(k);
  }

  void tapu(int a, int b, int64 x) {
    tapu(a, b, x, 0, 0, sz);
  }

  void set(int k, int64 x) {
    k += sz - 1;
    latte[k] = x;
    malta[k] = x;
    sum[k] = x;
    lcm[k] = x;
  }

  void build() {
    for(int k = sz - 2; k >= 0; k--) update(k);
  }
};

int main() {
  int N, Q;
  cin >> N >> Q;
  Ushitapunichiakun wara(N);
  for(int i = 0; i < N; i++) {
    int64 x;
    cin >> x;
    wara.set(i, x);
  }
  wara.build();
  for(int i = 0; i < Q; i++) {
    int t;
    cin >> t;
    if(t == 1) {
      int l, r, x;
      cin >> l >> r >> x;
      --l;
      wara.ushi(l, r, x);
    } else if(t == 2) {
      int l, r, x;
      cin >> l >> r >> x;
      --l;
      wara.tapu(l, r, x);
    } else if(t == 3) {
      int l, r;
      cin >> l >> r;
      --l;
      cout << wara.max_query(l, r) << "\n";
    } else {
      int l, r;
      cin >> l >> r;
      --l;
      cout << wara.sum_query(l, r) << "\n";
    }
  }
}
0