제출 #49219

#제출 시각아이디문제언어결과실행 시간메모리
49219amiGaraža (COCI17_garaza)C++14
160 / 160
1803 ms25920 KiB
#include <bits/stdc++.h> #define sz(c) int(c.size()) #define rep(i,a,b) for (int i=a; i<(b); ++i) #define per(i,a,b) for (int i=(b)-1; i>=(a); --i) using namespace std; using i64 = long long; using vii = vector<pair<int,int>>; template<typename T, typename Op> struct segment_tree { int n; Op op; T identity; vector<T> f; explicit segment_tree(int n_, Op op_=Op(), T identity_=T()) :n(n_), op(op_), identity(identity_), f(2*n, identity) {} T& operator[](int i) { return f[i+n]; } void build() { per(i,1,n) { f[i]=op(f[2*i],f[2*i+1]); } } void update(int i) { i+=n; for (i/=2; i>0; i/=2) { f[i]=op(f[2*i],f[2*i+1]); } } void update(int i, const T &x) { f[i+n]=x; update(i); } T query(int l, int r) { T L=identity; T R=identity; l+=n; r+=n; while (l<=r) { if (l%2==1) { L=op(L,f[l]); } if (r%2==0) { R=op(f[r],R); } l=(l+1)/2; r=(r-1)/2; } return op(L,R); } }; template<typename T, typename Op> segment_tree<T, Op> make_segment_tree(int n, Op op, T identity) { return segment_tree<T, Op>(n, op, identity); } struct node { i64 count; vii p,s; node():count(-1) {} node(i64 cc, vii pp, vii ss):count(cc),p(pp),s(ss) {} node(int x):count(x==1 ? 0 : 1),p{make_pair(x,1)},s{make_pair(x,1)} {} }; i64 merge_count(const vii &S, const vii &P) { i64 res=0,r=0,psum=0; per(l,0,sz(S)) { while (r<sz(P) && __gcd(S[l].first,P[r].first)>1) { psum+=P[r].second; r+=1; } res+=S[l].second*psum; } return res; } vii merge_comb(vii a, const vii &b) { int cur=a.back().first; for (const auto &x:b) { cur=__gcd(cur,x.first); if (cur==a.back().first) { a.back().second+=x.second; } else { a.emplace_back(cur,x.second); } } return a; } node merge_nodes(const node &L, const node &R) { if (L.count==-1) return R; if (R.count==-1) return L; i64 count=L.count+R.count+merge_count(L.s,R.p); auto p=merge_comb(L.p,R.p); auto s=merge_comb(R.s,L.s); return {count,p,s}; } int const MAXN=110000; int n,q; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cout<<fixed<<setprecision(10); cin>>n>>q; auto st = make_segment_tree(n,merge_nodes,node()); rep(i,0,n) { int x; cin>>x; st[i]=node(x); } st.build(); rep(iq,0,q) { int t,l,r; cin>>t>>l>>r; if (t==1) { st.update(l-1,node(r)); } else { cout<<st.query(l-1,r-1).count<<'\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...