제출 #992540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992540		LOLOLO	Garaža (COCI17_garaza)	C++17	160 / 160	414 ms	40300 KiB

garaza

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e5 + 10;
struct node{
    vector <pair <int, int>> pr, suff; 
    ll cc = 0;

    void build(int x) {
        pr.clear();
        suff.clear();
        if (x != 1) {
            cc = 1;
        } else {
            cc = 0;
        }

        pr.pb({x, 1});
        suff.pb({x, 1}); 
    }   
} seg[N * 4];
int a[N];

node merge(node A, node B) {
    node C;
    C.cc = A.cc + B.cc;
    C.pr = A.pr;
    int cur = A.pr.back().f, cnt = A.pr.back().s;
    C.pr.pop_back();

    for (auto x : B.pr) {
        if (x.f % cur) {
            C.pr.pb({cur, cnt});
            cnt = x.s;
            cur = __gcd(cur, x.f);
        } else {
            cnt += x.s;
        }
    }

    C.pr.pb({cur, cnt});

    C.suff = B.suff;
    cur = B.suff.back().f, cnt = B.suff.back().s;
    C.suff.pop_back();

    for (auto x : A.suff) {
        if (x.f % cur) {
            C.suff.pb({cur, cnt});
            cnt = x.s;
            cur = __gcd(cur, x.f);
        } else {
            cnt += x.s;
        }
    }

    C.suff.pb({cur, cnt});

    int j = 0;
    ll ss = 0;

    for (int i = sz(A.suff) - 1; i >= 0; i--) {
        while (j < sz(B.pr) && __gcd(B.pr[j].f, A.suff[i].f) > 1) {
            ss += B.pr[j].s;
            j++;
        }

        C.cc += ss * (ll)A.suff[i].s;
    }

    return C;
}

void build(int id, int l, int r) {
    if (l == r) {
        seg[id].build(a[l]);
        return;
    }

    int m = (l + r) / 2;
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);
    seg[id] = merge(seg[id * 2], seg[id * 2 + 1]); 
}

void upd(int id, int l, int r, int p, int v) {
    if (l == r) {
        seg[id].build(v);
        return;
    }

    int m = (l + r) / 2;
    if (m < p) {
        upd(id * 2 + 1, m + 1, r, p, v);
    } else {
        upd(id * 2, l, m, p, v);
    }

    seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
}

node get(int id, int l, int r, int u, int v) {
    if (l >= u && r <= v)
        return seg[id];


    int m = (l + r) / 2;
    if (m >= v) {
        return get(id * 2, l, m, u, v);
    }

    if (m < u) {
        return get(id * 2 + 1, m + 1, r, u, v);
    }

    return merge(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, 1, n);

    for (int i = 0; i < q; i++) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            upd(1, 1, n, l, r);
        }

        if (t == 2) {
            cout << get(1, 1, n, l, r).cc << '\n';
        }
    }
    return 0;
}  

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40
• Subtask 4: 40 / 40