There are n+1 (0 < n ≤ 10^{9}, indexed 0..n) houses lying on a straight street. One day, they are bombed by an enemy. CodeChef is designing defence systems to protect the street from bombing. Each defense system can protect all houses in some interval, and a house can be protected by more than one system. A defence system can be also moved at any time. By agents, CodeChef knows the bombing schedule of the enemy. Each time they bomb a house and CodeChef wants to know how many systems are protecting that house.

------ Input ------ 

The first line contains two integers n, m (0 < m ≤ 250 000).
Each of the m following lines follows one of these:
P u v: CodeChef adds a defence system protecting all houses from the u-th house to the v-th house (0 ≤ u ≤ v ≤ n). All systems will be indexed by order of appearance in the input, starting from 1.
M i d: CodeChef moves the i-th system by d houses, d < 0 means moving nearer the 0-th house, and d > 0 means moving away (that is, if the i-th system covers houses u through v, it is moved to instead cover houses w=u+d through t=v+d). After being moved the system will protect from the w-th house to t-th house where 0 ≤ w ≤ t ≤ n.
B x: The enemy bombs the x-th house.

------ Output ------ 

For each time of bombing by the enemy (by the appearance in the input), output on a single line a number of systems protecting that house.

----- Sample Input 1 ------ 
7 5
P 1 4
P 3 5
B 3
M 2 1
B 3
----- Sample Output 1 ------ 
2
1

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Range queries

Segment trees revisited


Solutions:
import sys

def update(bit, idx, val):
	while idx < len(bit):
		bit[idx] += val
		idx += idx & -idx

def sumb(bit, idx):
	ans = 0
	while idx > 0:
		ans += bit[idx]
		idx -= idx & -idx
	return ans

def input():
	return sys.stdin.readline().strip()

def mi():
	return int(input())

def MI():
	return map(int, input().split())

def LMI():
	return list(MI())
(n, m) = MI()
s = []
prot = []
prot1 = []
query = []
for _ in range(m):
	a = input().split()
	if a[0] == 'P':
		(b, c) = (int(a[1]), int(a[2]))
		s += [b, c]
		prot.append([b, c])
		prot1.append([b, c])
		query.append([a[0], b, c])
	elif a[0] == 'M':
		(b, c) = (int(a[1]), int(a[2]))
		[d, e] = prot1[b - 1]
		s += [d + c, e + c]
		prot1[b - 1] = [d + c, e + c]
		query.append([a[0], b - 1, c])
	else:
		b = int(a[1])
		s += [b]
		query.append([a[0], b, 0])
s.sort()
d = {}
cur = 1
for i in s:
	if i not in d:
		d[i] = cur
		cur += 1
bit = [0] * (cur + 10)
for (i, j, k) in query:
	if i == 'P':
		update(bit, d[j], 1)
		update(bit, d[k] + 1, -1)
	elif i == 'M':
		[b, c] = prot[j]
		update(bit, d[b], -1)
		update(bit, d[c] + 1, 1)
		update(bit, d[b + k], 1)
		update(bit, d[c + k] + 1, -1)
		prot[j] = [b + k, c + k]
	else:
		print(sumb(bit, d[j]))