- 0of 0 votes
You are given a rooted tree. The tree is not necessarily binary. The tree contains N nodes, labeled 1 to N. You are given the tree in the form of an array P[1..N] of size N. P[i] denotes label of the parent of node labeled i. For clarity, you may assume that the tree satisfies the following conditions.
The root of the tree is labeled 1. Hence P is set to 0.
The parent of node T will always have a label less than T. Hence P[i] < i will always be true.
All nodes contain a mutable value (or, more simply, a variable), which is initially set to 0.
You are asked to perform several operations of the following type
ADD X Y: add Y to the value at node X.
ADDUP X Y: add Y to the value at node X. Then, add Y to the value at P[X] (i.e. the parent of X). The, add Y to the value at P[P[X]] (i.e. the parent of P[X]).. and so on, till you add Y to the value at root.
After you have performed all the given operations, you are asked to answer several queries of the following type
VAL X: print the value at node X.
VALTREE X: print the sum of values at all nodes in the subtree rooted at X (including X).
The first line of input contains the number T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains the numbers N, M and Q respectively (separated by single space character). N depicts the number of nodes. M depicts the number of operations you must perform. Q depicts the number of queries you must answer.
The next N lines contain a number each, depicting the array P[1..N]. Of course the number on the first such line is always 0.
The next M lines contain description of the respective operation. An operation will be either "ADD X Y" or "ADDUP X Y" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the operations.
After the operations, the next Q lines contain description of the queries. A query will be either "VAL X" or "VALTREE X" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the queries.
Print the result of each query on a line by itself. Since the answer for some queries may be too large, please print the result modulo 1,000,000,007. Do not print any blank lines between test cases.
1 ≤ T ≤ 10
1 ≤ N ≤ 50000
1 ≤ M ≤ 50000
1 ≤ Q ≤ 50000
1 ≤ X ≤ N
1 ≤ Y ≤ 50000
The input file will be smaller than 2 MB.
5 5 3
ADD 1 10
ADD 2 20
ADD 3 30
ADD 4 40
ADDUP 5 50
7 4 5
ADD 6 76
ADDUP 1 49
ADD 4 48
ADDUP 2 59
In the first sample case, at the end of app the operations, the values at each of the nodes is as follows
Also, the sum of the values of all the nodes in the subtree rooted at each of the nodes is as follows
- 0of 0 votes
You are given a grid with 3 rows and N columns. Each cell in the grid contains the value 0 initially. You perform several operations of the following type on the grid
Pick a row, say r. Pick a start column and end column, say s and e. Of course 1 ≤ s ≤ e ≤ N. Now, set all values in the grid in row r, from column s to column e to 1.
After you perform all the operations, you wish to find subgrids in this grid (or rectangles, if you please) which contain only 1s. Most importantly, you wish to find the rectangle that has the largest area. Print the area of this rectangle.
The first line of input contains a number T, the number of test cases. The first line of each test case contains the number N and M respectively, separated by a single space. N is the number of columns in the grid. M is the number of operations you perform on the grid. Each of the next M lines contain three integers R, C1 and C2 respectively to describe the operation. R is the row in which the operation is performed. C1 and C2 are the start and end columns respectively. You may assume that 1 ≤ C1 ≤ C2 ≤ N.