IOPC1207  GM plants
The latest attraction for Techkriti 2112 is is a huge display of genetically modified plants. The arrangement consists of a cuboidal box of size N_{x} × N_{y} × N_{z} made of unit cubes. Each unit cube is identified using (x,y,z) coordinates  x ranges from 0 to N_{x}1 and so on  and contains a plant genetically modified to show fluorescence. The natural colour of the plants is green. However, on exposing a plant to laser light, it changes colour to red. What is more interesting is that on exposing a red plant to laser light again, it changes back to green and this continues.
The organisers have realised that they can use the display to make many coloured patterns. They have with them a laser light sheet which they can place along an axis and move in one direction, exposing many plants to light at once. For example, if the plane of the light sheet is kept as the y axis and it is moved from a to b, every plant with the y coordinate between a and b inclusive will turn from green to red or red to green. Every time the laser is operated, it is only the plants with one specific coordinate in a certain range which are affected.
You are told that initially all plants were green. Given the sequence of exposing plants to laser light, your task is to find the number of red coloured plants in certain cuboidal subregions of the display
Input
The first line of the input contains T, the number of test cases (T ≤ 10). Following this are the descriptions of the T test cases. The description of each test case starts with a line containing four space separated integers : N_{x}, N_{y}, N_{z} and Q (1 ≤ N_{x},N_{y},N_{z} ≤ 100000; Q ≤ 5000). The first three are the extents of the display in the three dimensions while Q is the number of queries which are to follow. Following this are Q lines, each describing a query. A query will be of one of the following forms :
 0 i j : expose all plants with x coordinates i ≤ x ≤ j to laser light
 1 i j : expose all plants with y coordinates i ≤ y ≤ j to laser light
 2 i j : expose all plants with z coordinates i ≤ z ≤ j to laser light
 3 x_{1} y_{1} z_{1} x_{2} y_{2} z_{2} : Report the number of red plants in the cuboidal region with (x_{1},y_{1},z_{1}) and (x_{2},y_{2},z_{2}) as diagonally opposite cells  ie, all red plants with x_{1} ≤ x ≤ x_{2}, y_{1} ≤ y ≤ y_{2} and z_{1} ≤ z ≤ z_{2}
All individual coordinates will be valid  ie, every x coordinate will be such that 0 ≤ x ≤ N_{x}1 and so on. Also, i ≤ j; x_{1} ≤ x_{2}; y_{1} ≤ y_{2} and z_{1} ≤ z_{2}
Output
For every query of the form 3 x_{1} y_{1} z_{1} x_{2} y_{2} z_{2} in the input, output the number of red plants with coordinates constrained by x_{1} ≤ x ≤ x_{2}, y_{1} ≤ y ≤ y_{2} and z_{1} ≤ z ≤ z_{2}
Example
Input: 1 3 4 5 5 0 1 2 1 2 3 3 0 0 0 1 2 3 2 3 4 3 1 1 1 2 2 2 Output: 12 4
hide comments
harshil nori:
20191202 15:33:39
How is the answer 12 for the first query? 

tommydong:
20190807 15:16:17
I rebuild the segment tree for every testcase, still got ac in one go :) 

tanmayak99:
20190203 10:31:32
Any test cases? Getting WA on 8th test case!


Numan :
20180811 08:23:06
I did everything on separate tree but queried on just one tree, I am a stupid piece of shit who wasted 40 mins on a problem, which was caused by just utter stupidity, don't be like me. Last edit: 20180811 08:24:15 

pranavraj219:
20171217 00:00:21
Great problem! 

fire_heart:
20160901 16:02:46
how could I write (l  r + 1) instead of (r  l + 1) _ 

pranavanurag:
20160828 11:41:02
Very interesting problem! 

j1k7_7(JaskamalKainth):
20160814 12:44:00
Easy! :) Nice Problem Raziman T V! :D 

Anurag Rai:
20160205 13:54:25
Getting SIGSEGV error repeatedly. The code is running fine though even for corner cases and all the cases I could think of. Help from the admin ? 

ujzwt4it:
20160106 16:29:32
deleted Last edit: 20160403 22:03:31 
Added by:  Raziman T V 
Date:  20120125 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  http://www.codechef.com/IOPC2012/ 