結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー ei1333333ei1333333
提出日時 2019-09-06 23:26:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 708 ms / 5,000 ms
コード長 3,468 bytes
コンパイル時間 2,607 ms
コンパイル使用メモリ 209,172 KB
実行使用メモリ 13,568 KB
最終ジャッジ日時 2024-09-22 19:36:29
合計ジャッジ時間 15,825 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 4 ms
5,376 KB
testcase_02 AC 4 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 606 ms
13,568 KB
testcase_12 AC 605 ms
13,568 KB
testcase_13 AC 436 ms
13,568 KB
testcase_14 AC 598 ms
13,568 KB
testcase_15 AC 634 ms
13,440 KB
testcase_16 AC 656 ms
13,568 KB
testcase_17 AC 708 ms
13,440 KB
testcase_18 AC 699 ms
13,568 KB
testcase_19 AC 304 ms
13,440 KB
testcase_20 AC 316 ms
13,440 KB
testcase_21 AC 313 ms
13,440 KB
testcase_22 AC 304 ms
13,568 KB
testcase_23 AC 321 ms
13,568 KB
testcase_24 AC 266 ms
13,440 KB
testcase_25 AC 277 ms
13,568 KB
testcase_26 AC 276 ms
13,568 KB
testcase_27 AC 272 ms
13,568 KB
testcase_28 AC 281 ms
13,440 KB
testcase_29 AC 577 ms
13,532 KB
testcase_30 AC 614 ms
13,440 KB
testcase_31 AC 663 ms
13,440 KB
testcase_32 AC 187 ms
13,568 KB
testcase_33 AC 246 ms
13,440 KB
testcase_34 AC 264 ms
13,568 KB
testcase_35 AC 248 ms
13,568 KB
testcase_36 AC 246 ms
13,440 KB
testcase_37 AC 250 ms
13,568 KB
権限があれば一括ダウンロードができます

ソースコード

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