[原创]SPOJ IITWPC4F - Gopu and the Grid Problem [线段树]【数据结构】

2017-01-11 00:06:46 Tabris_ 阅读数：241

https://blog.csdn.net/qq_33184171/article/details/54319679

-------------------------------------------------------------------------------------.
IITWPC4F - Gopu and the Grid Problem
no tags

Gopu is interested in the integer co-ordinates of the X-Y plane (0<=x,y<=100000). Each integer coordinate contain a lamp, initially all the lamps are in off mode. Flipping a lamp means switching it on if it is in off mode and vice versa. Maggu will ask gopu 3 type of queries.

Type 1: x l r, meaning: flip all the lamps whose x-coordinate are between l and r (both inclusive) irrespective of the y coordinate.

Type 2: y l r, meaning: flip all the lamps whose y-coordinate are between l and r (both inclusive) irrespective of the x coordinate.

Type 3: q x y X Y, meaning: count the number of lamps which are in ‘on mode’(say this number be A) and ‘off mode’ (say this number be B) in the region where x-coordinate is between x and X(both inclusive) and y-coordinate is between y and Y(both inclusive).
Input

First line contains Q-number of queries that maggu will ask to gopu. (Q <= 10^5)

Then there will be Q lines each containing a query of one of the three type described above.
Output

For each query of 3rd type you need to output a line containing one integer A.

Example

Input:
3
x 0 1
y 1 2
q 0 0 2 2

Output:
4
-------------------------------------------------------------------------------------.

x a b 将x轴坐标范围$[a,b]$的区域翻转,即0/1互换
y a b 将y轴坐标范围$[a,b]$的区域翻转,即0/1互换
q a b A B 查询$(a,b)(A,B)$范围内的区间中1的个数有多少.

-------------------------------------------------------------------------------.