PYRSUM2  Pyramid Sums 2
This is a harder version of PYRSUM
Tommy is stacking square blocks in columns labelled from 1 to 1000000 (10^{6}). Since it can be quite boring writing out the locations of every block he instead specifies a set of 2D pyramids that when built on top of each other will make the shape he wants. Pyramids always have height H=(W+1)/2 and take up N=H^{2} blocks so it is quite easy for him to work out how many blocks he will need in total from this description.
What is not so easy is working out how many blocks he will need to build in the space that occurs in the range between two columns (inclusive!). Given a set of instructions consisting of either
 “build [centre] [w]” (build another pyramid, width [w] with its midpoint at [centre]) or
 “count [left] [right]” (count the number of blocks added so far within the range of these columns inclusive)
you must try to answer the queries as quickly as possible.
Input
(1<=N<=200000), the number of operations to perform.
N lines, each containing one operation (as detailed above).
Output
Answer each count query on its own line, putting an additional blank line after each test case.
Please use 64bit counters as the result may overflow a 32bit container!
Example
Input: 3 build 5 3 build 6 5 count 4 7 Output: 12 Visualisation of example test case: BB BB BABB AAABB ^ ^
hide comments
hodobox:
20160705 05:26:16
@tsioftas: in easier version of this problem, it was indeed stated all pyramids have odd width 

tsioftas:
20160608 16:02:10
Are all the widths of the pyramids odd numbers? if not, then how is the pyramid built when the width is even as there is no centre? 

Robin Lee:
20140203 17:18:06
There is no point in submitting solutions copypasted from the Internet; these will all be disqualified. Last edit: 20140204 02:16:42 
Added by:  Robin Lee 
Date:  20110708 
Time limit:  0.392s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Self 