SPOJ IITWPC4F – Gopu and the Grid Problem(线段树)

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和y不超过1e5的x-y坐标系,初始每个点都为0。有三种操作:

1.x  l  r  代表把横坐标在[l,r]的区间上的点全翻转:1->0,0->1.

2.y  l  r 代表把纵坐标在[l,r]的区间上的点全翻转。

3.q x1 y1 x2 y2 询问在以(x1,y1)为左下角,(x2,y2)为右上角的矩形内有多少个1.

感觉还不错的一个题目,但是afk太久了,以至于翻转标记下传写挂调了大半个上午。

假如说我们知道(x,y)这个点左下方有r行是亮的,有c列是亮的。那么当前有x*c+y*r-2*x*y展灯是亮的。

我们可以分别以x轴和y轴建立线段树。然后弄个翻转标记什么的搞一搞就可以了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注