結果
| 問題 | No.880 Yet Another Segment Tree Problem |
| ユーザー |
 tonegawa
|
| 提出日時 | 2023-09-28 21:06:44 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,469 bytes |
| コンパイル時間 | 1,813 ms |
| コンパイル使用メモリ | 148,452 KB |
| 実行使用メモリ | 13,408 KB |
| 最終ジャッジ日時 | 2024-07-21 15:57:06 |
| 合計ジャッジ時間 | 7,640 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | AC | 74 ms
13,284 KB |
| testcase_33 | AC | 90 ms
13,184 KB |
| testcase_34 | AC | 96 ms
13,252 KB |
| testcase_35 | AC | 92 ms
13,176 KB |
| testcase_36 | AC | 92 ms
13,184 KB |
| testcase_37 | AC | 89 ms
13,184 KB |
ソースコード
#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, g;
Val(): sum(0), unique(minf), max(minf), g(0){}
Val(T x): sum(x), unique(x), max(x), g(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);
v.g = std::gcd(l.g, r.g);
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.g = 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.g && std::gcd(v.g, x.setx) == v.g;
}
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});
}
}
}
}