Raytracing

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 4.5s

Memory limit: 512M

Author:

insignificant

Problem type

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 $i$ ~i~ $(0 \le i < N)$ ~(0 \le i < N)~ and tree number $j$ ~j~ $(i \le j < N)$ ~(i \le j < N)~ that also have a height greater than or equal to $a$ ~a~ and less than or equal to $b$ ~b~, given the heights of the $N$ ~N~ 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 $N$ ~N~ $(1 \le N \le 2^{13})$ ~(1 \le N \le 2^{13})~, the number of trees.

On the second line, you will find $N$ ~N~ natural numbers $h_i$ ~h_i~ $(0 \le h_i < N)$ ~(0 \le h_i < N)~ separated by spaces.

On the third line, you will find $Q$ ~Q~ $(1 \le Q \le 2^{21})$ ~(1 \le Q \le 2^{21})~, the number of queries.

The queries can be one of two types:

$1$ ~1~ $i$ ~i~ $j$ ~j~ $a$ ~a~ $b$ ~b~, which is a question of the form "how many trees with index $k$ ~k~ $(0 \le i \le k \le j < N)$ ~(0 \le i \le k \le j < N)~ have height $h$ ~h~ $(a \le h \le b)$ ~(a \le h \le b)~?"
$2$ ~2~ $i$ ~i~ $h$ ~h~, which indicates that the tree at index $i$ ~i~ $(0 \le i < N)$ ~(0 \le i < N)~ has grown (or ungrown) to a height of $h$ ~h~ $(0 \le h < N)$ ~(0 \le h < N)~.

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

Output Specification

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

Subtasks

Subtask 1 [2/15]

$N \le 2^8$ ~N \le 2^8~

$Q \le 2^{10}$ ~Q \le 2^{10}~

Subtask 2 [3/15]

$N \le 2^{11}$ ~N \le 2^{11}~

Subtask 3 [10/15]

No additional constraints.

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

Sample Input 2

Sample Output 2

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation.

Comments

1

billsboard commented on Oct. 13, 2020, 11:15 p.m.

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

6

Ninjaclasher commented on Dec. 9, 2017, 10:45 p.m. ← edited →

Constraints Updated to Fail Brute Force Solutions

$N$ ~N~ has been raised from $2^{12}$ ~2^{12}~ to $2^{13}$ ~2^{13}~ and $Q$ ~Q~ has been raised from $2^{20}$ ~2^{20}~ to $2^{21}$ ~2^{21}~. In addition, the time limit is raised to 4.5 seconds from 2 seconds and the memory limit to 512M from 128M. Sorry for the inconvenience.

13

harry7557558 commented on March 2, 2020, 8: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.)

12

Dingledooper commented on March 2, 2020, 9:47 p.m.

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