一个线段树的算法题
来自interview street的算法题，
Quadrant Queries (30 points)
There are N points in the plane. The ith point has coordinates (xi, yi). Perform the following queries:
1) Reflect all points between point i and j both including along the X axis. This query is represented as "X i j"
2) Reflect all points between point i and j both including along the Y axis. This query is represented as "Y i j"
3) Count how many points between point i and j both including lie in each of the 4 quadrants. This query is represented as "C i j"
Input:
The first line contains N, the number of points. N lines follow.
The ith line contains xi and yi separated by a space.
The next line contains Q the number of queries. The next Q lines contain one query each, of one of the above forms.
All indices are 1 indexed.
Output:
Output one line for each query of the type "C i j". The corresponding line contains 4 integers; the number of points having indices in the range [i..j] in the 1st,2nd,3rd and 4th quadrants respectively.
Constraints:
1 <= N <= 100000
1 <= Q <= 1000000
You may assume that no point lies on the X or the Y axis.
All (xi,yi) will fit in a 32-bit signed integer
In all queries, 1 <=i <=j <=N
Sample Input:
4
1 1
-1 1
-1 -1
1 -1
5
C 1 4
X 2 4
C 3 4
Y 1 2
C 1 3
Sample Output:
1 1 1 1
1 1 0 0
0 2 0 1
Explanation
When a query says "X i j", it means that take all the points between indices i and j both including and reflect those points along the X axis. The i and j here have nothing to do with the co-ordinates of the points. They are the indices. i refers to point i and j refers to point j
'C 1 4' asks you to 'Consider the set of points having index in {1,2,3,4}. Amongst those points, how many of them lie in the 1st,2nd,3rd and 4th quads respectively?'
The answer to this is clearly 1 1 1 1.
Next we reflect the points between indices '2 4' along the X axis. So the new coordinates are :
1 1
-1 -1
-1 1
1 1
Now 'C 3 4' is 'Consider the set of points having index in {3,4}. Amongst those points, how many of them lie in the 1st,2nd,3rd and 4th quads respectively?' Point 3 lies in quadrant 2 and point 4 lies in quadrant 1.
So the answer is 1 1 0 0
需要使用线段树，但是我的实现：
class STree:
def __init__(self):
self.i = 0
self.j = 0
self.left = None
self.right = None
self.xFlip = 0 #延迟标记
self.yFlip = 0
self.quadNum = [0]*4
self.parent = None
def build(self, i, j, quadNum, quad):
#node interval and quadNum
self.i, self.j = i, j
for k in range(4):
self.quadNum[k] = quadNum[j][k] - quadNum[i-1][k]
if i == j:
return
mid = (i+j)//2
self.left = STree()
self.right = STree()
self.left.parent = self
self.right.parent = self
self.left.build(i, mid, quadNum, quad)
self.right.build(mid+1, j, quadNum, quad)
#type 0->x. 1->y
def updateQuad(self, type):
curQuadNum = [0]*4
if type == 0:
curQuadNum[0], curQuadNum[1], curQuadNum[2], curQuadNum[3] = \
self.quadNum[3], self.quadNum[2], self.quadNum[1], self.quadNum[0]
else:
curQuadNum[0], curQuadNum[1], curQuadNum[2], curQuadNum[3] = \
self.quadNum[1], self.quadNum[0], self.quadNum[3], self.quadNum[2]
#print(self.quadNum)
for k in range(4):
dQuadNum[k] = curQuadNum[k] - self.quadNum[k]
#print('type %d %d %d' %(type, self.i, self.j))
#print(dQuadNum)
#change self and ancestor
if dQuadNum == [0, 0, 0, 0]:
return
parent = self
while parent:
parent.quadNum = [u+v for u, v in zip(dQuadNum, parent.quadNum)]
parent = parent.parent
return
def updateNodeX(self):
self.quadNum[0], self.quadNum[1], self.quadNum[2], self.quadNum[3] = \
self.quadNum[3], self.quadNum[2], self.quadNum[1], self.quadNum[0]
def updateNodeY(self):
self.quadNum[0], self.quadNum[1], self.quadNum[2], self.quadNum[3] = \
self.quadNum[1], self.quadNum[0], self.quadNum[3], self.quadNum[2]
#将延迟标记向子节点推
def pushDownLable(self):
if self.xFlip == 1:
self.updateNodeX()
if self.left: self.left.xFlip = 1 - self.left.xFlip
if self.right: self.right.xFlip = 1 - self.right.xFlip
self.xFlip = 0
if self.yFlip == 1:
self.updateNodeY()
if self.left: self.left.yFlip = 1 - self.left.yFlip
if self.right: self.right.yFlip = 1 - self.right.yFlip
self.yFlip = 0
#查询
def query(self, i, j):
#push down the label
#update delay
self.pushDownLable()
if i<=self.i and j>=self.j:
#print('node %d %d %d %d' %(i, j, self.i, self.j))
#print('%d %d %d %d' %(self.quadNum[0], self.quadNum[1], self.quadNum[2], self.quadNum[3]))
return self.quadNum
mid = (self.i+self.j)//2
#contain this node
rst = [0]*4
if self.left and i<= mid:
lrst = self.left.query(i, j)
rst = [u+v for u,v in zip(rst, lrst)]
if self.right and j>=mid+1:
rrst = self.right.query(i, j)
rst = [u+v for u,v in zip(rst, rrst)]
return rst
#翻转线段
def updateFlip(self, i, j, type):
self.pushDownLable()
if i<=self.i and j>=self.j:
#update parent
#print('xflip %d %d %d %d' %(i, j, self.i, self.j))
self.updateQuad(type)
#marker delay to children
if self.left and type == 0:
self.left.xFlip = 1 - self.left.xFlip
if self.right and type == 0:
self.right.xFlip = 1 - self.right.xFlip
if self.left and type == 1:
self.left.yFlip = 1- self.right.yFlip
if self.right and type == 1:
self.right.yFlip = 1 - self.right.yFlip
return
mid = (self.i+self.j)//2
if self.left and i<= mid:
self.left.updateFlip(i, j, type)
if self.right and j>=mid+1:
self.right.updateFlip(i, j, type)
N = int(raw_input())
quad = [0]*(N+1)
for i in range(1, N+1):
t = raw_input().split(' ')
x, y = int(t[0]), int(t[1])
if x > 0 and y > 0:
quad[i] = 0
elif x<0 and y > 0:
quad[i] = 1
elif x<0 and y<0:
quad[i] = 2
else:
quad[i] = 3
#cache the number
quadNum = [[0 for i in range(4)] for j in range(N+1)]
for i in range(1,N+1):
for j in range(4):
quadNum[i][j] = quadNum[i-1][j]
quadNum[i][quad[i]] += 1
tree = STree()
tree.build(1, N, quadNum, quad)
M = int(raw_input())
for i in range(M):
t = raw_input().split(' ')
q, j, k = t[0], int(t[1]), int(t[2])
if q == 'C':
num = tree.query(j, k)
print('%d %d %d %d' %(num[0], num[1], num[2], num[3]))
elif q == 'X':
tree.updateFlip(j, k, 0)
elif q == 'Y':
tree.updateFlip(j, k, 1)
self.left.xFlip = 1 - self.left.xFlip
if self.right and type == 0:
self.right.xFlip = 1 - self.right.xFlip
if self.left and type == 1:
self.left.yFlip = 1- self.right.yFlip
if self.right and type == 1:
self.right.yFlip = 1 - self.right.yFlip
---------------------------
self.left.yFlip = 1- self.right.yFlip
[解决办法]
我当年写oj的时候测定下来python要比c慢10~20倍。如果oj上没有调整的话那超时是正常的。
