Submission #81189

#	Time	Username	Problem	Language	Result	Execution time	Memory
81189		ngot23	Garaža (COCI17_garaza)	C++11	160 / 160	1171 ms	237556 KiB

garaza

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define Task ""
using namespace std;
const int N=100005;
int n, Q, a[N];
struct node {
    int demP, demS, P[35], S[35], cntP[35], cntS[35];
    long long res;
    node() {
        demP=demS=0;
        res=0;
        memset(P, 0, sizeof P);
        memset(S, 0, sizeof S);
        memset(cntP, 0, sizeof cntP);
        memset(cntS, 0, sizeof cntS);
    }
    node (node &lef, node &rig) {
        rep(i, 1, lef.demP) {
            P[i]=lef.P[i];
            cntP[i]=lef.cntP[i];
        }
        /// tinh prefix gcd
        demP=lef.demP;
        int id=1;
        int gcd=lef.P[lef.demP];
        for(; id<=rig.demP ; ++id) {
            int xx=__gcd(gcd, rig.P[id]);
            if(xx!=gcd) break;
            cntP[demP]+=rig.cntP[id];
        }
        while(id<=rig.demP) {
            P[++demP]=__gcd(gcd, rig.P[id]);
            cntP[demP]=rig.cntP[id];
            int id2=id+1;
            for(; id2<=rig.demP ; ++id2) {
                int xx=__gcd(gcd, rig.P[id2]);
                if(xx!=P[demP]) break;
                cntP[demP]+=rig.cntP[id2];
            }
            id=id2;
        }

        rep(i, 1, rig.demS) {
            S[i]=rig.S[i];
            cntS[i]=rig.cntS[i];
        }
        /// tinh suffix gcd
        demS=rig.demS;
        id=1;
        gcd=rig.S[rig.demS];
        for(; id<=lef.demS ; ++id) {
            int xx=__gcd(gcd, lef.S[id]);
            if(xx!=gcd) break;
            cntS[demS]+=lef.cntS[id];
        }
        while(id<=lef.demS) {
            S[++demS]=__gcd(gcd, lef.S[id]);
            cntS[demS]=lef.cntS[id];
            int id2=id+1;
            for(; id2<=lef.demS ; ++id2) {
                int xx=__gcd(gcd, lef.S[id2]);
                if(xx!=S[demS]) break;
                cntS[demS]+=lef.cntS[id2];
            }
            id=id2;
        }

        /// hop res 2 cay
        res=lef.res+rig.res;
        id=0;
        int sum=0;
        for(int i=lef.demS ; i ; --i) {
            while(__gcd(lef.S[i], rig.P[id+1])!=1&&id<rig.demP) { ++id; sum+=rig.cntP[id]; }
            res+=1ll*sum*lef.cntS[i];
        }

    }
};
node it[N*4];

void build(int l, int r, int id) {
    if(l==r) {
        it[id].demP=it[id].demS=it[id].cntP[1]=it[id].cntS[1]=1;
        it[id].P[1]=it[id].S[1]=a[l];
        if(a[l]!=1) it[id].res=1;
        else it[id].res=0;
        return;
    }
    int mid=(r+l)>>1;
    build(l, mid, id*2);
    build(mid+1, r, id*2+1);
    it[id]=node(it[id*2], it[id*2+1]);
}

void update(int l, int r, int id, int x) {
    if(l==r) {
        it[id].demP=it[id].demS=it[id].cntP[1]=it[id].cntS[1]=1;
        it[id].P[1]=it[id].S[1]=a[l];
        if(a[l]!=1) it[id].res=1;
        else it[id].res=0;
        return;
    }
    int mid=(r+l)>>1;
    if(x<=mid) update(l, mid, id*2, x);
    else update(mid+1, r, id*2+1, x);
    it[id]=node(it[id*2], it[id*2+1]);
}

node get(int l, int r, int id, int u, int v) {
    if(r<u||v<l) return node();
    if(u<=l&&r<=v) return it[id];
    int mid=(r+l)>>1;
    node m1=get(l, mid, id*2, u, v);
    node m2=get(mid+1, r, id*2+1, u, v);
    return node(m1, m2);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(Task".inp", "r", stdin);
    //freopen(Task".out", "w", stdout);
    cin >> n >> Q;
    rep(i, 1, n) cin >> a[i];

    build(1, n, 1);
    while(Q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if(t==1) {
            a[x]=y;
            update(1, n, 1, x);
        } else {
            cout << get(1, n, 1, x, y).res << '\n';
        }
    }
    return 0;
}

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