Submission #257463

#	Time	Username	Problem	Language	Result	Execution time	Memory
257463		NONAME	Garaža (COCI17_garaza)	C++14	160 / 160	2041 ms	34828 KiB

garaza

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = int(1e5) + 500;

int n, q;
int a[N];

struct tree {
    tree *L, *R;
    vector <pair <int, int> > pf, sf;
    ll cnt;

    tree() {
        L = R = 0;
        cnt = 0;
        pf.clear(); sf.clear();
    }

    void merge(tree *Left, tree *Right) {
        vector <pair <int, int> > lft, rgt;
        (this -> pf).clear();
        (this -> sf).clear();
        lft = (Left -> pf);
        rgt = (Right -> pf);
        for (int i = 0; i < int(lft.size()); ++i)
            (this -> pf).push_back(lft[i]);

        for (int i = 0; i < int(rgt.size()); ++i) {
            int gcd = __gcd(rgt[i].first, (this -> pf).back().first);
            if (gcd == (this -> pf).back().first) (this -> pf).back().second += rgt[i].second;
                else (this -> pf).push_back(make_pair(gcd, rgt[i].second));
        }

        lft = (Left -> sf);
        rgt = (Right -> sf);

        for (int i = 0; i < int(rgt.size()); ++i)
            (this -> sf).push_back(rgt[i]);

        for (int i = 0; i < int(lft.size()); ++i) {
            int gcd = __gcd(lft[i].first, (this -> sf).back().first);
            if (gcd == (this -> sf).back().first) (this -> sf).back().second += lft[i].second;
                else (this -> sf).push_back(make_pair(gcd, lft[i].second));
        }

        (this -> cnt) = (Left -> cnt) + (Right -> cnt);
        lft = (Left -> sf);
        rgt = (Right -> pf);

        vector <int> pref(int(rgt.size()), 0);
        pref.clear();

        for (int i = 0; i < int(rgt.size()); ++i)
            pref[i] = (i - 1 < 0 ? 0 : pref[i - 1]) + rgt[i].second;

        int p = int(rgt.size()) - 1;

        for (int i = 0; i < int(lft.size()); ++i) {
            while (p >= 0 && __gcd(lft[i].first, rgt[p].first) == 1)
                --p;
            if (p < 0)
                break;

            (this -> cnt) += lft[i].second * 1ll * pref[p];
        }
    }

    void build(int tl, int tr) {
        if (tl > tr)
            return;
        if (tl == tr) {
            cnt = (a[tl] != 1);
            pf.push_back(make_pair(a[tl], 1));
            sf.push_back(make_pair(a[tl], 1));
            return;
        }

        int md = (tl + tr) >> 1;
        L = new tree();
        R = new tree();

        L -> build(tl, md);
        R -> build(md + 1, tr);

        merge(L, R);
    }

    void update(int tl, int tr, int p, int vl) {
        if (tl == tr) {
            a[tl] = vl;
            cnt = (a[tl] != 1);
            pf[0] = sf[0] = make_pair(a[tl], 1);
            return;
        }

        int md = (tl + tr) >> 1;
        if (p <= md) L -> update(tl, md, p, vl);
            else R -> update(md + 1, tr, p, vl);

        merge(L, R);
    }

    pair <ll, pair <vector <pair <int, int> >, vector <pair <int, int> > > > query(int tl, int tr, int ql, int qr) {
        vector <pair <int, int> > npf, nsf;
        npf.clear(); nsf.clear();
        if ((tl > tr) || (ql > tr) || (tl > qr))
            return make_pair(0ll, make_pair(npf, nsf));

        if ((tl >= ql) && (tr <= qr))
            return make_pair(cnt, make_pair(pf, sf));

        int md = (tl + tr) >> 1;
        auto res1 = L -> query(tl, md, ql, qr);
        auto res2 = R -> query(md + 1, tr, ql, qr);
        ll cur_res = 0;


        vector <pair <int, int> > lft, rgt;
        lft = res1.second.first;
        rgt = res2.second.first;
        for (int i = 0; i < int(lft.size()); ++i)
            npf.push_back(lft[i]);

        for (int i = 0; i < int(rgt.size()); ++i) {
            if (npf.empty()) {
                npf.push_back(rgt[i]);
                continue;
            }
            int gcd = __gcd(rgt[i].first, npf.back().first);
            if (gcd == npf.back().first) npf.back().second += rgt[i].second;
                else npf.push_back(make_pair(gcd, rgt[i].second));
        }

        lft = res1.second.second;
        rgt = res2.second.second;

        for (int i = 0; i < int(rgt.size()); ++i)
            nsf.push_back(rgt[i]);

        for (int i = 0; i < int(lft.size()); ++i) {
            if (nsf.empty()) {
                nsf.push_back(lft[i]);
                continue;
            }
            int gcd = __gcd(lft[i].first, nsf.back().first);
            if (gcd == nsf.back().first) nsf.back().second += lft[i].second;
                else nsf.push_back(make_pair(gcd, lft[i].second));
        }

        cur_res = res1.first + res2.first;
        lft = res1.second.second;
        rgt = res2.second.first;

        vector <int> pref(int(rgt.size()), 0);
        pref.clear();

        for (int i = 0; i < int(rgt.size()); ++i)
            pref[i] = (i - 1 < 0 ? 0 : pref[i - 1]) + rgt[i].second;

        int p = int(rgt.size()) - 1;

        for (int i = 0; i < int(lft.size()); ++i) {
            while (p >= 0 && __gcd(lft[i].first, rgt[p].first) == 1)
                --p;
            if (p < 0)
                break;

            cur_res += lft[i].second * 1ll * pref[p];
        }


        return make_pair(cur_res, make_pair(npf, nsf));
    }

    //void show(int tl, int tr) {
        //cerr << tl + 1 << " " << tr + 1 << " " << cnt << "\n";
        //for (auto i : pf)
            //cerr << i.first << " " << i.second << "\n";
        //cerr << "---------\n";
        //for (auto i : sf)
            //cerr << i.first << " " << i.second << "\n";
        //cerr << "\n";
    //}

    //void result(int tl, int tr) {
        //if (tl > tr)
            //return;
        //if (tl == tr) {
            //show(tl, tr);
            //return;
        //}

        //int md = (tl + tr) >> 1;
        //L -> result(tl, md);
        //R -> result(md + 1, tr);

        //show(tl, tr);
    //}
} t;

int main() {
    fast_io;

    cin >> n >> q;
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    t.build(0, n - 1);
    //t.result(0, n - 1);
    //cerr << "!!!!!\n";

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x, y;
            cin >> x >> y;
            --x;
            t.update(0, n - 1, x, y);
            //t.result(0, n - 1);
            //cerr << "!!!!!!\n";
        } else {
            int x, y;
            cin >> x >> y;
            --x, --y;

            cout << (t.query(0, n - 1, x, y)).first << "\n";
        }
    }
}

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