一个线段树的算法题
来自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 numberquadNum = [[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]] += 1tree = 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)