結果

問題 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  
実行時間 743 ms / 5,000 ms
コード長 3,468 bytes
コンパイル時間 2,827 ms
コンパイル使用メモリ 210,472 KB
実行使用メモリ 13,528 KB
最終ジャッジ日時 2023-10-24 02:39:28
合計ジャッジ時間 16,079 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,372 KB
testcase_01 AC 4 ms
4,372 KB
testcase_02 AC 5 ms
4,372 KB
testcase_03 AC 5 ms
4,372 KB
testcase_04 AC 4 ms
4,372 KB
testcase_05 AC 4 ms
4,372 KB
testcase_06 AC 3 ms
4,372 KB
testcase_07 AC 4 ms
4,372 KB
testcase_08 AC 4 ms
4,372 KB
testcase_09 AC 4 ms
4,372 KB
testcase_10 AC 4 ms
4,372 KB
testcase_11 AC 633 ms
13,528 KB
testcase_12 AC 617 ms
13,528 KB
testcase_13 AC 440 ms
13,528 KB
testcase_14 AC 616 ms
13,528 KB
testcase_15 AC 656 ms
13,528 KB
testcase_16 AC 681 ms
13,528 KB
testcase_17 AC 743 ms
13,528 KB
testcase_18 AC 725 ms
13,528 KB
testcase_19 AC 308 ms
13,528 KB
testcase_20 AC 316 ms
13,528 KB
testcase_21 AC 318 ms
13,528 KB
testcase_22 AC 307 ms
13,528 KB
testcase_23 AC 326 ms
13,528 KB
testcase_24 AC 267 ms
13,528 KB
testcase_25 AC 281 ms
13,528 KB
testcase_26 AC 279 ms
13,528 KB
testcase_27 AC 275 ms
13,528 KB
testcase_28 AC 283 ms
13,528 KB
testcase_29 AC 597 ms
13,528 KB
testcase_30 AC 636 ms
13,528 KB
testcase_31 AC 672 ms
13,528 KB
testcase_32 AC 188 ms
13,528 KB
testcase_33 AC 248 ms
13,528 KB
testcase_34 AC 263 ms
13,528 KB
testcase_35 AC 252 ms
13,528 KB
testcase_36 AC 251 ms
13,528 KB
testcase_37 AC 251 ms
13,528 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