一个线段树的算法题
来自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)

给出的是wrong answer，查了很久一直没有查出来。
请帮忙一下，我怀疑自己在算法上有问题。
非常感谢。
[解决办法]
蚵蚵。稍微调试了两下就发现问题了。你肯定要哭死
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
---------------------------
self.left.yFlip = 1- self.right.yFlip
[解决办法]
我当年写oj的时候测定下来python要比c慢10~20倍。如果oj上没有调整的话那超时是正常的。