| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 473312 | Ahmed_Solyman | Garaža (COCI17_garaza) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
using namespace std;
typedef long long ll;
ll segTree[(4*100000)+5];
ll arr[100000+5];
void build(ll l,ll r,ll p)
{
if(l>r)return;
if(l==r){
segTree[p]=arr[l];
return;
}
ll mid=(l+r)/2;
build(l,mid,p*2);
build(mid+1,r,p*2+1);
segTree[p]=__gcd(segTree[p*2],segTree[p*2+1])>1;
}
ll query(ll l,ll r,ll p,ll query_l,ll query_r)
{
if(query_r<l || query_l>r){
return 1e18;
}
if(l>=query_l && r<=query_r){
return segTree[p];
}
ll mid=(l+r)/2;
return __gcd(query(l,mid,p*2,query_l,query_r),query(mid+1,r,p*2+1,query_l,query_r))>!;
}
void update(ll l,ll r,ll p,ll idx,ll value)
{
if(l>r)return;
if(l==r){
segTree[p]=value;
return;
}
ll mid=(l+r)/2;
if(idx>mid){
update(mid+1,r,p*2+1,idx,value);
}
else{
update(l,mid,p*2,idx,value);
}
segTree[p]=__gcd(segTree[p*2],segTree[p*2+1])>1;
}
int main()
{
ll n,q;cin>>n>>q;
for(ll i=1;i<=n;i++)cin>>arr[i];
build(1,n,1);
while(q--){
ll type,x,y;cin>>type>>x>>y;
x++;
if(type==1){
update(1,n,1,x,y);
}
else{
cout<<query(1,n,1,x,y)<<endl;
}
}
return 0;
}