help-the-avengers-6

With the help of the tessaract, the Chitauri army is ready to attack planet Earth. It's finally time when the Avengers must get together to save the planet. Captain Fury, along with the beautiful Agent Maria Hill is trying to work out a plan. He is well aware that Loki, the leader of the enemies has identified certain prime spots to attack. Each spot on the planet is identified by a specific number. A prime spot is one that is represented by a prime number. Now, the Captain's intelligence team has provided him with a list of N locations A[1.....N]. From time to time, the team also replaces one location in the list with another one. Every now and then, Captain Fury asks Maria to report the number of prime locations between positions X & Y (inclusive) in the list so that he could position the Avengers at those locations. Now the beautiful lady is tired. Help her.

Input:
The first line consists of an integer T, the number of test cases. Then the description of T test cases follow. The first line of each test case consists of an integer N, the number of locations in the list given to Doctor Fury. The next line contains N space separated integers. The next line contains Q, the total number of times either the list is changed or the Captain asks Maria his query.
Then Q lines follow, each of the line having one of the following format

i) C\; X\; Y - where C is UpperCase alphabet 'C' representing a change in the list, X represents the list index where the change is to be made, Y represents the new location that is added to the above index
e.g. C\; 4\; 123

ii) A\; X\; Y - where A is Uppercase alphabet 'A' representing asking prime spots between indexes X and Y (inclusive) in the list
e.g. A\; 1\; 12

Output:

For each of the query for asking number of prime spots, output a single integer, the answer to Captain Fury's question.

Constraints:

1 ≤ T ≤ 10  
1 ≤ N ≤ 32000
1 ≤ A[i] ≤ 10^6
1 ≤ Q ≤ 20000

*NOTE: *
Large Input File (~2 MB)

Use 1-based indexing for all list queries

SAMPLE INPUT
1
10
1 3 18 960 22 17 15 31 99 231
5
A 1 10
C 3 17
C 5 23
A 1 10
A 1 5

SAMPLE OUTPUT
3
5
3

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Bit manipulation

Range queries

Segment trees revisited


Solutions:
import math


class SegmentTree(object):
	def __init__(self, start, end):
		self.start = start
		self.end = end
		self.max_value = {}
		self.sum_value = {}
		self.len_value = {}
		self._init(start, end)

	def add(self, start, end, weight=1):
		if start < self.start or end > self.end:
			return False
		self._add(start, end, weight, self.start, self.end)
		return True

	def query_max(self, start, end):
		return self._query_max(start, end, self.start, self.end)

	def query_sum(self, start, end):
		return self._query_sum(start, end, self.start, self.end)

	def query_len(self, start, end):
		return self._query_len(start, end, self.start, self.end)

	""""""
	def _init(self, start, end):
		self.max_value[(start, end)] = 0
		self.sum_value[(start, end)] = 0
		self.len_value[(start, end)] = 0
		if start < end:
			mid = start + (end - start) / 2
			self._init(start, mid)
			self._init(mid+1, end)

	def _add(self, start, end, weight, in_start, in_end):
		key = (in_start, in_end)
		if in_start == in_end:
			self.max_value[key] += weight
			self.sum_value[key] += weight
			self.len_value[key] = 1 if self.sum_value[key] > 0 else 0
			return

		mid = in_start + (in_end - in_start) / 2
		if mid >= end:
			self._add(start, end, weight, in_start, mid)
		elif mid+1 <= start:
			self._add(start, end, weight, mid+1, in_end)
		else:
			self._add(start, mid, weight, in_start, mid)
			self._add(mid+1, end, weight, mid+1, in_end)
		self.max_value[key] = max(self.max_value[(in_start, mid)], self.max_value[(mid+1, in_end)])
		self.sum_value[key] = self.sum_value[(in_start, mid)] + self.sum_value[(mid+1, in_end)]
		self.len_value[key] = self.len_value[(in_start, mid)] + self.len_value[(mid+1, in_end)]

	def _query_max(self, start, end, in_start, in_end):
		if start == in_start and end == in_end:
			ans = self.max_value[(start, end)]
		else:
			mid = in_start + (in_end - in_start) / 2
			if mid >= end:
				ans = self._query_max(start, end, in_start, mid)
			elif mid+1 <= start:
				ans = self._query_max(start, end, mid+1, in_end)
			else:
				ans = max(self._query_max(start, mid, in_start, mid),
						self._query_max(mid+1, end, mid+1, in_end))
		return ans

	def _query_sum(self, start, end, in_start, in_end):
		if start == in_start and end == in_end:
			ans = self.sum_value[(start, end)]
		else:
			mid = in_start + (in_end - in_start) / 2
			if mid >= end:
				ans = self._query_sum(start, end, in_start, mid)
			elif mid+1 <= start:
				ans = self._query_sum(start, end, mid+1, in_end)
			else:
				ans = self._query_sum(start, mid, in_start, mid) + self._query_sum(mid+1, end, mid+1, in_end)
		return ans

	def _query_len(self, start, end, in_start, in_end):
		if start == in_start and end == in_end:
			ans = self.len_value[(start, end)]
		else:
			mid = in_start + (in_end - in_start) / 2
			if mid >= end:
				ans = self._query_len(start, end, in_start, mid)
			elif mid+1 <= start:
				ans = self._query_len(start, end, mid+1, in_end)
			else:
				ans = self._query_len(start, mid, in_start, mid) + self._query_len(mid+1, end, mid+1, in_end)

		return ans
		
def check(n):
	if n == 2:
		return 1
	if n%2 == 0 or n <= 1:
		return 0
	sqr = int(math.sqrt(n)) + 1
	for divisor in range(3, sqr, 2):
		if n%divisor == 0:
			return 0
	return 1


def solve():
	N = int(input())
	s = SegmentTree(1,N)
	nums = [int(x) for x in input().split()]
	
	for i in range(N):
		s.add(i+1,i+1,check(nums[i]))
		
	Q = int(input())
	for _ in range(Q):
		[a,x,y] = input().split()
		x=int(x)
		y=int(y)
		if a=="A":
			print(s.query_sum(x,y))
		else:
			old = s.query_sum(x,x)
			s.add(x,x,check(y)-old)



def main():
	for _ in range(int(input())):
		solve()

main()


import math
def is_prime(a):
	if(a==2 or a==3 or a==5 or a==7):
		return True
	elif (a==1 or a==4 or a==6 or a==8 or a==9):
		return False
	return all(a % i for i in range(2, int(math.sqrt(a)+1)))

t=eval(input())
while(t):
	n=eval(input())
	s=input()
	l1=s.split(" ")
	num=[]
	prime=[]
	for i in range (0,n):
		num.append(int(l1[i]));
		if is_prime(int(l1[i])):
			prime.append(1)
		else:
			prime.append(0);
	q=eval(input())
	while(q):
		s=input()
		l1=s.split(" ")
		if l1[0]=='A':
			print(prime[int(l1[1])-1:int(l1[2])].count(1));
		else:
			num[int(l1[1])-1]=int(l1[2])
			if is_prime(int(l1[2])):
				prime[int(l1[1])-1]=1
			else:
				prime[int(l1[1])-1]=0

		q=q-1
	t=t-1