PYRSUM - Pyramid Sums

no tags 

This is an easier version of PYRSUM2

Tommy is stacking square blocks in columns labelled from 1 to 1000000 (106). 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=H2 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

First line: (1<=T<=20), the number of test cases.

Within each test case:

  1. (1<=N<=1000), the number of operations to perform.
  2. 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 64-bit counters as the result may overflow a 32-bit container!

Example

Input:
4
3
build 5 3
build 6 5
count 4 7
2
build 200 99
count 151 151
4
build 2 1
count 1 1
count 2 2
count 1 2
6
build 5000 3999
count 1 10000
build 2 1
build 3 1
count 2 2
count 2 3

Output:
12

1

0
1
1

4000000
1
2

Visualisation of first test case:
----BB---
----BB---
---BABB--
---AAABB-
   ^  ^

hide comments
alucard_01: 2018-12-25 07:12:17

Can someone explain the arrangement in the 1st test case..??

.:: Pratik ::.: 2013-03-14 23:38:27

Are widths always odd? What if there are even widths?
For width=4, is the the expected output:
.##.
####

RE: There are only odd-width pyramids. Even-width pyramids could only be expressed using non-integer centrepoints, which would displease Tommy.

Last edit: 2011-07-09 13:00:20

Added by:Robin Lee
Date:2011-07-07
Time limit:0.583s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self