fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <string.h>
  4. #include <vector>
  5.  
  6. #define N 1000000
  7.  
  8. using namespace std ;
  9.  
  10. int sieve[1000001]	;
  11. int array[100001]	;
  12.  
  13. struct node{
  14.  
  15. 	int value	;
  16. 	bool flag	;						// flag = 1 ; if all the element in the range which each internal node represent are 1 
  17.  
  18. };
  19.  
  20. struct node ST[400002]	;
  21.  
  22. void primes (){
  23.  
  24. 	sieve[1] = 1	;
  25. 	sieve[2] = 2	;
  26. 	sieve[0] = 1	;
  27.  
  28. 	for(int i = 4; i <= N; i += 2)
  29. 		sieve[i] = 2	;
  30.  
  31. 	for (int i = 3; i * i <= N; i += 2)
  32.  
  33. 		if (!sieve[i]){
  34.  
  35. 			sieve[i] = i;
  36. 			for (int j = i * i; j <= N; j += 2 * i)
  37. 				if(!sieve[j])   						// ensure not to overwrite already filled entries
  38. 					sieve[j] = i;
  39. 		}
  40.  
  41.     for (int i = 3; i <= N; i += 2)						// Only prime numbers are left which are filled with 0's
  42.         if (!sieve[i])
  43.             sieve[i] = i    ;
  44.  }
  45.  
  46. void make(int low, int high, int pos){
  47.  
  48. 	if (low == high){
  49.  
  50. 		ST[pos].value = sieve[array[low]]	;			// building Segment Tree on LeastPrimeDivisor of Ai's
  51.  
  52. 		if (array[low] == 1)
  53. 			ST[pos].flag = 1	;
  54. 		else
  55. 			ST[pos].flag = 0	;
  56.  
  57. 		return ;
  58. 	}
  59.  
  60. 	int mid = (low+high) / 2	;
  61. 	make(low, mid, 2*pos + 1)	;
  62. 	make(mid+1, high, 2*pos + 2);
  63. 	ST[pos].value = max(ST[2*pos+1].value, ST[2*pos+2].value)	;
  64. 	ST[pos].flag = 0	;
  65.  
  66. 	return	;
  67.  
  68. }
  69.  
  70. void update(int L, int R, int low, int high, int pos){
  71.  
  72. 	if (low > R || high < L)
  73. 		return	;
  74.  
  75. 	if (ST[pos].flag)									// Return if the leaf nodes in the subtree rooted at node 'pos' contains all 1's, no update is needed
  76. 		return 	;
  77.  
  78. 	if (low == high){									// leaf node
  79.  
  80. 		array[low] /= sieve[array[low]]	;						// change ST[pos].value and array[low] value accordingly
  81. 		ST[pos].value = sieve[array[low]]	;
  82. 		if (array[low] == 1)
  83. 			ST[pos].flag = 1	;
  84. 		return	;
  85. 	}
  86.  
  87. 	int mid = (low+high) /	2	;
  88.  
  89. 	if (mid >= R)
  90. 		update(L, R, low, mid, 2*pos+1)	;
  91.  
  92. 	else if (mid < L)
  93. 		update(L, R, mid+1, high, 2*pos+2)	;
  94.  
  95. 	else{
  96.  
  97. 		update(L, R, low, mid, 2*pos+1)	;
  98. 		update(L, R, mid+1, high, 2*pos+2)	;
  99.  
  100. 	}
  101.  
  102. 	ST[pos].value = max(ST[2*pos + 1].value, ST[2*pos + 2].value)	;
  103.  
  104. 	if (ST[2*pos + 1].flag && ST[2*pos + 2].flag)							// put the flag = 1 for node 'pos', if flag of both child of the node, i.e, left.flag and right.flag, both are 1 
  105. 		ST[pos].flag = 1	;
  106.  
  107. 	return	;	
  108. }
  109.  
  110. int query(int L, int R, int low, int high, int pos){					//Simple query function
  111.  
  112. 	if (low > R || high < L)
  113. 		return -1	;
  114.  
  115. 	if (L <= low && high <= R)
  116. 		return ST[pos].value	;
  117.  
  118. 	int mid = (low+high) / 2	;
  119. 	return max(query(L, R, low, mid, 2*pos+1), query(L, R, mid+1, high, 2*pos+2))	;
  120.  
  121. }
  122.  
  123. int main(){
  124.  
  125. 	primes()	;
  126. 	int n, m, t, q, L, R ;
  127. 	ios_base::sync_with_stdio(false);   cin.tie(0)  ;
  128. 	scanf("%d", &t) 	;
  129. 	while(t--){
  130.  
  131. 		scanf("%d %d", &n, &m)	;
  132. 		memset(array, 0, sizeof(array))	;
  133. 		memset(&ST, 0, sizeof(ST))	;
  134.  
  135. 		for (int i = 0; i < n; i++)
  136. 				scanf("%d", &array[i])	;
  137.  
  138. 		make(0, n-1, 0)	;					// building segment on 'array' 
  139.  
  140. 		for (int i = 0; i < m ; i++){
  141. 			scanf("%d %d %d", &q, &L, &R)	;
  142.  
  143. 			L--;		// 0 based indexed
  144. 			R--;
  145.  
  146. 			L = min(L, R)	;			// Asserting L <= R, not neccessary if input is well behaved
  147. 			R = max(L, R)	;
  148.  
  149. 			if (!q)
  150.  
  151. 				update(L, R, 0, n-1, 0)	;
  152.  
  153. 			else
  154.  
  155. 				printf("%d ", query(L, R, 0, n-1, 0))	;
  156. 		}
  157. 		printf("\n")	;
  158. 	}
  159.  
  160. 	return 0	;
  161. }
Success #stdin #stdout 0s 10304KB
comments ()
stdin
copy 
2
6 7
2 5 8 10 3 44
1 2 6
0 2 3
1 2 6
0 4 6
1 1 6
0 1 6
1 4 6
2 2
1 3
0 2 2
1 1 2
stdout
copy 
5 3 5 11 
1
https://ideone.com/8P3WHD
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!