이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |