oj.uz

답안 #639373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
639373 2022-09-09T17:36:13 Z inksamurai Garaža (COCI17_garaza) C++17
160 / 160
 2189 ms 48064 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3xaMC2q ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
//e

using vp=vec(pii);

struct N{
	int val,len;
	vp fr,bk;
	N(int _val=0,int _len=0,vp vc={}):
	val(_val),len(_len),fr(vc),bk(vc){}
};

int f(int si,int n){
	return si*n-(n*(n-1))/2;
}

struct segtree{
	int n;
	vec(N) seg;
	segtree(int _n=0){
		init(_n);
	}
	void init(int _n){
		n=_n;
		seg.resize(n*4);
	}
	N merge(N l,N r){
		if(!sz(l.fr)){
			return r;
		}else if(!sz(r.fr)){
			return l;
		}
		
		N res;
		res.val=l.val+r.val;
		res.len=l.len+r.len;

		vec(pii) leftover;
		//from back to front
		rep(i,sz(l.bk)){
			//gcd
			int g=l.bk[i].se;
			if(g==1) continue;
			//suffix sum in l node
			int now=0;
			per(j,i+1){
				now+=l.bk[j].fi;
			}
			bool pok=0;
			rep(j,sz(r.fr)){
				g=gcd(g,r.fr[j].se);
				if(g==1){
					pok=1;
					res.val+=f(now,l.bk[i].fi);
					break;
				}
				now+=r.fr[j].fi;
			}
			if(!pok){
				leftover.pb(l.bk[i]);
			}
		}

		res.bk=r.bk;
		//from leftover should be pushed in res.bk
		if(sz(leftover)){
			int g=0;
			rep(i,sz(r.bk)){
				g=gcd(g,r.bk[i].se);
			}

			vec(pii) rbts=res.bk;
			rep(i,sz(leftover)){
				g=gcd(g,leftover[i].se);
				assert(g!=-1);
				if(g==rbts.back().se){
					rbts.back().fi+=leftover[i].fi;
				}else{
					rbts.pb(pii(leftover[i].fi,g));
				}
			}
			res.bk=rbts;
		}

		res.fr=l.fr;
		//merge front of l node with r.bk
		{
			int now=0,g=0;
			rep(i,sz(l.fr)){
				now+=l.fr[i].fi;
				g=gcd(g,l.fr[i].se);
			}
			if(now==l.len and g!=1){
				rep(i,sz(r.fr)){
					g=gcd(g,r.fr[i].se);
					if(g==res.fr.back().se){
						res.fr.back().fi+=r.fr[i].fi;
					}else{
						res.fr.pb(pii(r.fr[i].fi,g));
					}
					if(g==1) break;
				}
			}
		}
		return res;
	}
	void set(int node,int l,int r,int pos,int v){
		if(l==r-1){
			seg[node].fr.clear();
			seg[node].bk.clear();
			seg[node]=N(0,1,{{1,v}});
			return;
		}
		int m=(l+r)/2;
		if(pos<m){
			set(node*2+1,l,m,pos,v);
		}else{
			set(node*2+2,m,r,pos,v);
		}
		seg[node]=merge(seg[node*2+1],seg[node*2+2]);
	}
	void set(int pos,int v){
		set(0,0,n,pos,v);
	}
	N prod(int node,int l,int r,int _l,int _r){
		if(l>=_r or r<=_l){
			return N();
		}
		if(_l<=l and r<=_r){
			return seg[node];
		}
		int m=(l+r)/2;
		N vl=prod(node*2+1,l,m,_l,_r);
		N vr=prod(node*2+2,m,r,_l,_r);
		return merge(vl,vr);
	}
	int prod(int l,int r){
		N res=prod(0,0,n,l,r);
		int ans=res.val;
		int now=0;
		for(auto p:res.bk){
			if(p.se==1) break;
			// print("go",p.se);
			now+=p.fi;
			ans+=f(now,p.fi);
		}
		return ans;
	}
};

signed main(){
_3xaMC2q;
	int n,q;
	cin>>n>>q;
	vi a(n);
	rep(i,n){
		cin>>a[i];
	}
	segtree seg(n);
	rep(i,n){
		seg.set(i,a[i]);
	}
	// print(seg.prod(0,n));
	rep(i,q){
		int t;
		cin>>t;
		if(t==2){
			int l,r;
			cin>>l>>r;
			l-=1;
			print(seg.prod(l,r));
		}else{
			int id,v;
			cin>>id>>v;
			id-=1;
			seg.set(id,v);
		}
	}
}

Subtask #1
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 724 KB Output is correct
2 Correct 36 ms 1716 KB Output is correct
3 Correct 47 ms 2616 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 9976 KB Output is correct
2 Correct 464 ms 14256 KB Output is correct
3 Correct 319 ms 13388 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 827 ms 23492 KB Output is correct
2 Correct 802 ms 24228 KB Output is correct
3 Correct 677 ms 26932 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2189 ms 47120 KB Output is correct
2 Correct 1546 ms 48064 KB Output is correct
3 Correct 1235 ms 44520 KB Output is correct