Untitled

1
mail@pastecode.io avatar
unknown
c_cpp
2 years ago
2.2 kB
8
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

int n, q;
long long arr[100011];
long long tree[400011];
long long lazy[400011];
long long ps[100011];

long long gcd(long long a, long long  b){
    if(b==0) return a;
    return gcd(b,a%b);
}

void init(int node, int start, int end){
    if(start==end){
        tree[node] = arr[start];
        return;
    }
    int mid = (start+end)/2;
    init(2*node, start, mid);
    init(2*node+1, mid+1, end);
    tree[node] = tree[2*node] + tree[2*node+1];
    return;
}

void lazy_update(int node, int start, int end){
    if(lazy[node]){
        tree[node] = (end-start+1)*lazy[node];
        if (start!=end){
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
    }
    lazy[node] = 0;
    return;
}

void update(int node, int start, int end, int left, int right, long long value){
    lazy_update(node, start, end);
    if(end< left || right < start) return;
    if(left <= start && end <= right){
        tree[node] += (end-start+1) * value;
        if(start!=end){
            lazy[2*node] += value;
            lazy[2*node+1] += value;
        }
        return;
    }
    int mid = (start+end)/2;
    update(2*node, start, mid, left, right, value);
    update(2*node+1, mid+1, end, left, right, value);
    tree[node] = tree[2*node] + tree[2*node+1];
    return;
}

// gcd 이용해야 함;
long long query(int node, int start, int end, int left, int right){
    lazy_update(node, start, end);
    if(end < left || right < start) return 0;
    if(left <= start && end <= right) return tree[node];
    int mid = (start+end)/2;
    long long lSum = query(2*node, start, mid, left, right);
    long long rSum = query(2*node+1, mid+1, end, left, right);
    return gcd(lSum, rSum);
}


int main(void){
    cin >> n;
    for(int i=0;i<n;i++) cin >> arr[i];
    init(1,0,n-1);
    cin >> q;
    long order;
    int x, y;
    while(q--){
        cin >> order;
        if(order==0){
            cin >> x >> y;
            cout << query(1, 0, n-1, x-1,y-1) << '\n';
        }
        else{
            cin >> x >> y;
            update(1, 0, n-1, x-1, y-1, order);
        }
    }
}