shil-and-round-numbers

Shil likes Round numbers very much . A  number is called Round number if its non-negative and its first and last digits are same. For example  0 , 3 , 343 and  50005 are round numbers whereas 1000 is not  a round number. Shil has  an array A1 , A2  .. AN . He wants to answer Q queries of following two type :
1 l r  : Find total number of round numbers in range [l, r]
2 i K  : Update i^th element of array A to K  i.e perform the  operation Ai = K. 
Since you are the friend of Shil , he asks for your help .

INPUT:
First line consists of two integers N and Q. Next line consists of N integers A1 , A2  .. AN. Next line consists of Q queries. Each query consists of three integers as mentioned in the problem.

OUTPUT: 
For each query of type 2 , output total number of round numbers in range [l,r].

CONSTRAINTS:
1 ≤ N , Q ≤ 2*10^5
-10^18 ≤ Ai ≤ 10^18 
1 ≤ l,r ≤ N
-10^18 ≤ K ≤ 10^18

SAMPLE INPUT
5 5 
1 2 33 456 111
1 1 2
1 1 5
2 1 6
2 2 1000
1 1 5

SAMPLE OUTPUT
2
4
3

Explanation

Out of all the initial numbers given in array A :- 1,2,33,111 are round numbers .
For 1^st query , there are two round numbers - A[1] and A[2].
For 2^st query , there are 4 round numbers - A[1] , A[2] , A[3] , A[5].
In   3^rd query , we are updating 1st position with 6 , which is a round number.
In   4^th query , we are updating 2nd position with 1000 , which isn't a round number.  
For 5^th query , there are 3 round numbers - A[1] , A[3] and  A[5].

Source: hackerearth | Difficulty: EASY
Tags: Bit manipulation

Data structures

Mathematics


Solutions:
def update(x,v):
	while x<=N:
		bit[x]+=v
		x += x&-x

def query(x):
	total = 0;
	while x>0:
		total+=bit[x]
		x -= x&-x
	return total

(N,Q) = [int(s) for s in input().strip().split(" ")]
S = [s for s in input().strip().split(" ")]
X = []
bit = [0 for j in range(N+1)]
for i in range(N):
	if S[i][0]==S[i][-1]:
		X.append(True)
		update(i+1,1)
	else:
		X.append(False)

for i in range(Q):
	(a,b,c) = [s for s in input().strip().split(" ")]
	a = int(a)
	b = int(b)
	if a==2:
		new = (c[0]==c[-1])
		if X[b-1]!=new:
			X[b-1]=new
			if new:
				update(b,1)
			else:
				update(b,-1)
	else:
		b= b-1
		c= int(c)
		print(query(c)-query(b))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
(n,q) = [int(v) for v in input().strip().split(' ')]
arr = [int(v) for v in input().strip().split(' ')]
tree=[0]*(n+1)
nums=[-1]*(n+1)


def ndigs(num):
	if num==0:
		return 0
	return 1+ndigs(num/10)
	
def firstDig(num, digs):
	if digs==1:
		return num%10
	return firstDig(num/10,digs-1)
	
def isRound(num):
	if num<0:
		return False
	(n1,n2)=(num%10,firstDig(num,ndigs(num)))
	return n1==n2

def update(tree, ind, num):
	(b1,b2) = (isRound(num),isRound(nums[ind]))
	if b1 and b2:
		return
	elif not b1 and not b2:
		return
	elif b1 and not b2:
		updateVal(tree,ind,1)
	else:
		updateVal(tree,ind,-1)
	nums[ind]=num


def updateVal(tree,ind,val):
	while ind<=n:
		tree[ind]+=val
		ind += ind&(-ind)

def query(tree,l,r):
	return qr(tree,r)-qr(tree,l-1)

def qr(tree,pos):
	ans = 0
	while pos>0:
		ans+=tree[pos]
		pos-=pos&(-pos)
	return ans

for i in range(1,n+1):
	update(tree,i,arr[i-1])


while q>0:
	q-=1
	(t,v1,v2) = [int(v) for v in input().strip().split(' ')]
	if t==1:
		ans = query(tree,v1,v2)
		print(ans)
	else:
		update(tree,v1,v2)