범위의 최대공약수 쿼리 최적화..
글쓴이: ddddewang / 작성시간: 목, 2022/04/14 - 12:05오전
백준 12858번입니다.
구간의 최대공약수를 쿼리하는 문제고요, 레이지 프로파게이션을 이용해서 구현했습니다.
그런데 최대공약수는 구간합과는 달라서 리프노드까지 탐색해야합니다. 그래서 결국에는 세그먼트 트리의 역할은 레이지 프로파게이션하는 것 이외에는 없습니다... 그러니까 엄청 비효율적이라는 것이죠. 이 문제를 어떻게 해결하면 좋을까요?
#include <iostream> using namespace std; typedef long long l; l off,tree[300000],lazy[300000],n,input[100000],Q; l gcd(l a,l b){ if(!b)return a; return gcd(b,a%b); } void lazy_update(l node,l s,l e) { if(lazy[node]>0){ if(s==e){ tree[node]+=lazy[node]; } if(s!=e){ lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; } lazy[node]=0; } } void update(l node,l s,l e,l left,l right,l value){ lazy_update(node,s,e); if(right<s||left>e)return; if(left<=s&&e<=right){ if(s==e){ tree[node]+=value; } if(s!=e){ lazy[node*2]+=value; lazy[node*2+1]+=value; } return; } l mid=(s+e)/2; update(node*2,s,mid,left,right,value); update(node*2+1,mid+1,e,left,right,value); if(tree[node*2]==0)tree[node]=tree[node*2+1]; else if(tree[node*2+1]==0)tree[node]=tree[node*2]; else tree[node]=gcd(tree[node*2],tree[node*2+1]); } l query(l node,l s,l e,l left,l right){ lazy_update(node,s,e); if(right<s||left>e)return 0; if(left<=s&&e<=right&&s==e)return tree[node]; l mid=(s+e)/2,lv=query(node*2,s,mid,left,right),rv=query(node*2+1,mid+1,e,left,right); //if(lv==0)return rv; //if(rv==0)return lv; return gcd(lv,rv); } void init(){ off=1; for(;off<n;)off*=2; for(l i=off;i<off+n;i++)tree[i]=input[i-off]; for(l i=off+n;i<off*2;i++)tree[i]=0; for(l i=off-1;i>=1;i--){ if(tree[i*2]==0)tree[i]=tree[i*2+1]; else if(tree[i*2+1]==0)tree[i]=tree[i*2]; else tree[i]=gcd(tree[i*2],tree[i*2+1]); } } void print(){ puts("\n***************"); for(int i=1;i<off*2;i++)cout<<tree[i]<<' '; puts("\n***************"); } int main(){ cin>>n; for(l i=0;i<n;i++)cin>>input[i]; init(); cin>>Q; for(l i=0;i<Q;i++){ l T,A,B; cin>>T>>A>>B; if(T==0){ printf("%lld\n",query(1,1,n,A,B)); } else{ update(1,1,n,A,B,T); //print(); } } }
Forums: