백준14899 수열과 쿼리 19

작성일 | In

문제 링크

  • http://icpc.me/14899

사용 알고리즘

  • 세그먼트 트리 비츠

풀이

수열과 쿼리 28와 비슷하게 풀면 됩니다.

구간에 나눗셈을 할 때 tag_condition을 두 개 잡을 겁니다.

  1. [(구간의 min) / d] == [(구간의 max) / d]
  2. (구간의 min + 1) == (구간의 max)

1번의 경우에는 전체 구간을 d로 나눠도 상관 없습니다.
만약 1번에 해당하지 않고 2번에만 해당하는 경우에는 [(구간의 min) / d] - (구간의 min)을 빼주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll inf = 1e18;

struct Node{
    Node(){}
    Node(ll mn, ll mx, ll sum) : mn(mn), mx(mx), sum(sum) {}
    ll mn, mx, sum;
} tree[1 << 18];

ll tmp1[1 << 18], tmp2[1 << 18];

Node merge(Node a, Node b){
    return {min(a.mn, b.mn), max(a.mx, b.mx), a.sum + b.sum};
}

void push(int node, int s, int e){
    if(tmp2[node] <= -inf){
        tree[node].mx += tmp1[node];
        tree[node].mn += tmp1[node];
        tree[node].sum += (e-s+1)*tmp1[node];
        if(s ^ e){
            tmp1[node*2] += tmp1[node];
            tmp1[node*2+1] += tmp1[node];
        }
    }else{
        tree[node].mx = tree[node].mn = tmp1[node] + tmp2[node];
        tree[node].sum = (e-s+1) * (tmp1[node] + tmp2[node]);
        if(s ^ e){
            tmp1[node*2] = tmp1[node];
            tmp1[node*2+1] = tmp1[node];
            tmp2[node*2] = tmp2[node];
            tmp2[node*2+1] = tmp2[node];
        }
    }
    tmp1[node] = 0, tmp2[node] = -inf;
}

void add(int node, int s, int e, int l, int r, ll v){
    push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){
        tmp1[node] = v;
        push(node, s, e);
        return;
    }
    int m = s + e >> 1;
    add(node*2, s, m, l, r, v);
    add(node*2+1, m+1, e, l, r, v);
    tree[node] = merge(tree[node*2], tree[node*2+1]);
}

void div(int node, int s, int e, int l, int r, ll d){
    push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){
        if(floor((double)tree[node].mn / d) == floor((double)tree[node].mx / d)){
            tmp2[node] = floor((double)tree[node].mn / d);
            push(node, s, e);
            return;
        }
        if(tree[node].mn + 1 == tree[node].mx){
            tmp1[node] = floor((double)tree[node].mn / d) - tree[node].mn;
            push(node, s, e);
            return;
        }
    }
    int m = s + e >> 1;
    div(node*2, s, m, l, r, d);
    div(node*2+1, m+1, e, l, r, d);
    tree[node] = merge(tree[node*2], tree[node*2+1]);
}

Node query(int node, int s, int e, int l, int r){
    push(node, s, e);
    if(r < s || e < l) return {inf, -inf, 0};
    if(l <= s && e <= r) return tree[node];
    int m = s + e >> 1;
    return merge(query(node*2, s, m, l, r), query(node*2+1, m+1, e, l, r));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    for(int i=0; i<(1<<18); i++) tmp2[i] = -inf;
    int n, q; cin >> n >> q;
    for(int i=0; i<n; i++){
        int t; cin >> t;
        add(1, 0, n-1, i, i, t);
    }
    while(q--){
        int op; cin >> op;
        if(op == 1){
            ll a, b, c; cin >> a >> b >> c; add(1, 0, n-1, a, b, c);
        }else if(op == 2){
            ll a, b, c; cin >> a >> b >> c; div(1, 0, n-1, a, b, c);
        }else{
            int a, b; cin >> a >> b;
            Node now = query(1, 0, n-1, a, b);
            if(op == 3) cout << now.mn << "\n";
            else cout << now.sum << "\n";
        }
    }
}