백준17476 수열과 쿼리 28

작성일 | In

문제 링크

  • http://icpc.me/17476

사용 알고리즘

  • Segment Tree Beats

풀이

1, 3번 쿼리는 구간 합 구하기 2 문제와 똑같습니다. 2번 쿼리만 잘 처리하면 됩니다.

루트 연산은 값이 빠르게 감소합니다. 그렇기 때문에 여러 번 연산할수록 같은 값이 많아지게 됩니다.
그러므로 점점 break-condition이나 tag-condition에 걸리지 않을 확률이 감소하게 됩니다.
믿음을 갖고 세그비츠를 사용하면 됩니다.

전체 코드

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
106
107
108
109
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

int n;
ll tmp1[1 << 18];
ll tmp2[1 << 18];

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

void push(int node, int s, int e){
    if(!tmp1[node] && !tmp2[node]) return;
    if(!tmp2[node]){
        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] = tmp2[node] = 0;
}

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

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 sq(int node, int s, int e, int l, int r){
    push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){
        if(floor(sqrt(tree[node].mn)) == floor(sqrt(tree[node].mx))){
            tmp2[node] = floor(sqrt(tree[node].mx));
            push(node, s, e);
            return;
        }
        if(tree[node].mn + 1 == tree[node].mx){
            tmp1[node] = floor(sqrt(tree[node].mn)) - tree[node].mn;
            push(node, s, e);
            return;
        }
    }
    int m = s + e >> 1;
    sq(node*2, s, m, l, r);
    sq(node*2+1, m+1, e, l, r);
    tree[node] = merge(tree[node*2], tree[node*2+1]);
}

int main(){
    //freopen("in", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        ll t; cin >> t;
        add(1, 1, n, i, i, t);
    }

    int q; cin >> q;
    while(q--){
        int op; cin >> op;
        if(op == 1){
            int a, b, c; cin >> a >> b >> c;
            add(1, 1, n, a, b, c);
        }else if(op == 2){
            int a, b; cin >> a >> b;
            sq(1, 1, n, a, b);
        }else{
            int a, b; cin >> a >> b;
            query(1, 1, n, a, b);
            cout << query(1, 1, n, a, b) << "\n";
        }
        //for(int i=1; i<=n; i++) cout << query(1, 1, n, i, i) << " "; cout << "\n";
    }
}