## Raytracing

View as PDF

Points: 10 (partial)
Time limit: 4.5s
Memory limit: 512M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

After our alien visitors landed, the scientific community is in uproar over the fascinating trees that grew in the wake of our otherworldly visitors. These trees have a trunk diameter of zero and have no leaves or roots. How photosynthesis occurs in these trees if it occurs at all is up to speculation. In fact, these trees can be better modeled as mathematical rays. Your job, as the newest hire of the Logging Company, is to produce an image of the forest viewed from above if the trees were light rays. Just kidding. We don't do that to our new hires.

Ahem. Your actual task today is to find the number of trees between tree number and tree number that also have a height greater than or equal to and less than or equal to , given the heights of the trees. However, the trees grow occasionally and your answers must be adjusted to account for growth. Unsurprisingly, it's even possible for a tree to ungrow.

#### Input Specification

On the first line you will find , the number of trees.

On the second line you will find natural numbers separated by spaces.

On the third line you will find , the number of queries.

The queries can be one of two types:

• , which is a question of the form "how many trees with index have height ?"
• , which indicates that the tree at index has grown (or ungrown) to a height of

The subsequent lines each contain one query of the form described above.

#### Output Specification

Output one natural number per line to answer each of the queries.

No further restrictions

#### Sample Input 1

10
3 3 9 4 7 6 6 6 0 3
10
1 2 4 4 5
1 4 8 2 3
2 5 3
1 4 7 0 6
1 1 4 1 2
1 0 2 0 2
1 0 9 0 4
2 5 6
1 0 7 0 1
2 3 3

#### Sample Output 1

1
0
3
0
0
6
0

#### Sample Input 2

4
2 2 0 0
16
1 0 3 0 1
2 0 1
1 0 3 0 1
1 1 2 0 1
1 0 3 0 2
2 0 0
2 2 2
2 1 0
1 1 3 2 2
2 1 3
1 1 2 0 3
2 0 2
1 0 1 1 2
2 3 3
1 1 3 1 1
2 3 2

#### Sample Output 2

2
3
1
4
1
2
1
0

• commented on Oct. 13, 2020, 7:15 p.m.

Apparently brute force still passes. Maybe update the constraints again?

• commented on Dec. 9, 2017, 5:45 p.m.

Constraints Updated to Fail Brute Force Solutions

has been raised from to and has been raised from to . In addition, the time limit is raised to 10 seconds from 4 seconds and the memory limit to 512M from 128M. Sorry for the inconvenience.

• commented on March 2, 2020, 3:18 p.m. edit 2

I still pass it with brute force in C++11 after enabling optimization using preprocessing command.

(However, I got Compile Error in CCC contest after adding #pragma GCC optimize("Ofast") in the beginning of my source code.)

• commented on March 2, 2020, 4:47 p.m.

Thanks for the tip, now I have the fastest submission using brute force.

• commented on Dec. 11, 2017, 8:10 p.m.

Except d still passed