fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX=500020;
  5.  
  6. int tree[MAX];
  7. int A[100005];
  8.  
  9. void Build_Tree(int node, int st, int end)
  10. {
  11. 	if(st == end)
  12. 	{
  13. 		tree[node] = A[st];
  14. 		return ;
  15. 	}
  16. 	int mid = (st+end)/2;
  17. 	Build_Tree(node*2, st, mid);
  18.  
  19. 	Build_Tree(node*2+1, mid+1, end);
  20.  
  21. 	tree[node] = __gcd(tree[2*node], tree[2*node+1]);
  22. 	return;
  23. }
  24.  
  25. void update(int node, int st, int end, int idx, int value)
  26. {
  27. 	if(st == end)
  28. 	{  
  29. 		tree[node] = value; 
  30. 		A[idx] = value;
  31. 		return ;
  32. 	}
  33.  
  34. 	int mid = (st+end)/2;
  35. 	if(idx<=mid)
  36. 	{
  37. 		update(2*node, st, mid, idx, value);
  38. 	}
  39. 	else
  40. 	{
  41. 		update(2*node+1, mid+1, end, idx, value);
  42. 	}
  43.  
  44. 	tree[node] = __gcd(tree[2*node], tree[2*node+1]); 
  45. 	return ;
  46. }
  47.  
  48. int RangeGcd(int node, int st, int end, int l, int r)
  49. {
  50. 	if(l <= st && end <= r )
  51. 	{
  52. 		return tree[node];
  53. 	}
  54.  
  55. 	if(st>r || end<l)
  56. 		return 0;
  57.  
  58. 	int mid = (st+end)/2;
  59.  
  60. 	int ans1 = RangeGcd(2*node, st, mid, l, r);
  61. 	int ans2 = RangeGcd(2*node+1, mid+1, end, l, r);	
  62. 	return __gcd(ans1, ans2);	
  63. }
  64.  
  65. int main()
  66. {
  67. 	int n,q,l,r,a;
  68. 	cin>>n>>q;
  69. 	for(int i=0;i<MAX;i++)
  70. 		tree[i]=0;
  71. 	for(int i=1;i<=n;i++) {
  72. 		cin>>A[i];
  73. 	}
  74. 	Build_Tree(1,1,n);
  75. 	while(q--)
  76. 	{
  77. 		cin>>a>>l>>r;
  78. 		if(a==0)
  79. 		{
  80. 			cout<<RangeGcd(1,1,n,l,r)<<endl;
  81. 		}
  82. 		else
  83. 		{
  84. 			update(1,1,n,l,r);
  85. 		}
  86. 	}
  87. 	return 0;
  88. }
Success #stdin #stdout 0s 5560KB
comments (?)
stdin
copy 
10 6
2 6 18 3 15 21 50 60 7 2
0 1 3
1 6 210
0 5 8
1 1 3
0 1 6
0 2 10
stdout
copy 
2
5
3
1
https://ideone.com/tB82Q5
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!