제출 #380088

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

garaza

#include <bits/stdc++.h>
#define N 100005
using namespace std;
struct Node{
    long long val,lp,rp;
    vector<pair<int,int>> l,r;
    Node(){
        val = 0,lp=0,rp=0;
        l = r = {{0,0}};
    }
    Node(long long x,long long a,long b,vector<pair<int,int>>y,vector<pair<int,int>>z){
        val = x;
        lp = a;
        rp = b;
        l = y;
        r = z;
    }
};
Node t[4*N];
Node merge(Node a,Node b){
    if(a.val == -1)return b;
    if(b.val == -1)return a;
    Node ret = a;
    ret.val += b.val;
    ret.r = b.r;
    ret.rp = b.rp;

    int cnt = 0;
    int n = b.l.size();
    while(cnt < n){
        if(__gcd(ret.l.back().first,b.l[cnt].first) == ret.l.back().first){
            ret.l.back().second = b.l[cnt++].second;
            continue;
        }
        ret.l.push_back({__gcd(ret.l.back().first,b.l[cnt].first),b.l[cnt].second});
        cnt++;
    }
    
    cnt = 0;
    n = a.r.size();
    while(cnt < n){
        if(__gcd(ret.r.back().first,a.r[cnt].first) == ret.r.back().first){
            ret.r.back().second = a.r[cnt++].second;
            continue;
        }
        ret.r.push_back({__gcd(ret.r.back().first,a.r[cnt].first),a.r[cnt].second});
        cnt++;
    }

    cnt = a.r.size()-1;
    int bef = b.lp;
    for(auto u:b.l){
        while(cnt >= 0 && __gcd(u.first,a.r[cnt].first) == 1){
            cnt--;
        }
        if(cnt < 0)break;
        ret.val += (u.second-bef + 1) * (a.rp - a.r[cnt].second + 1);
        bef = u.second+1;
    }

    return ret;
}
void upd(int v,int l,int r,int pos,int val){
    if(l == r){
        t[v] = Node((val != 1),l,r,{{val,l}},{{val,l}});
        return;
    }
    int m = (l+r)/2;
    if(pos <= m){
        upd(v*2,l,m,pos,val);
    }
    else upd(v*2+1,m+1,r,pos,val);
    t[v] = merge(t[v*2],t[v*2+1]);
}

Node get(int v,int tl,int tr,int l,int r){
    if(tr < l || r < tl ){
        return Node(-1,-1,-1,{{-1,-1}},{{-1,-1}});
    }
    if(l <= tl && tr <= r){
        return t[v];
    }
    int tm = (tl+tr)/2;
    return merge( get(v*2,tl,tm,l,r), get(v*2+1,tm+1,tr,l,r));
}

void solve(){
    int n,q;
    cin >> n >> q;
    for(int i=1;i<=n;i++){
        int a;
        cin >> a;
        upd(1,1,n,i,a);
    }
    /*
    for(auto u:t[1].l){
        cout << u.first << " " << u.second << endl;
    }*/
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int pos,val;
            cin >> pos >> val;
            upd(1,1,n,pos,val);
        }
        if(type == 2){
            int l,r;
            cin >>  l >> r;
            cout << get(1,1,n,l,r).val << endl;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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