evostorm96
BAN USER- 0of 0 votes
AnswersYou 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.
- evostorm96 in India
The root of the tree is labeled 1. Hence P[1] 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).
Input
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.
Output
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.
Constraints
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.
Sample Input
2
5 5 3
0
1
1
1
3
ADD 1 10
ADD 2 20
ADD 3 30
ADD 4 40
ADDUP 5 50
VAL 3
VALTREE 3
VALTREE 1
7 4 5
0
1
2
2
2
1
2
ADD 6 76
ADDUP 1 49
ADD 4 48
ADDUP 2 59
VALTREE 1
VALTREE 5
VAL 5
VALTREE 2
VAL 2
Sample Output
80
130
250
291
0
0
107
59
Explanation
In the first sample case, at the end of app the operations, the values at each of the nodes is as follows
1: 60
2: 20
3: 80
4: 40
5: 50
Also, the sum of the values of all the nodes in the subtree rooted at each of the nodes is as follows
1: 250
2: 20
3: 130
4: 40
5: 50| Report Duplicate | Flag | PURGE
Directi Software Developer - 0of 0 votes
AnswersYou 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
- evostorm96 in India
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.
Input
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.| Report Duplicate | Flag | PURGE
Directi Software Developer
Repdorarwoods, Kuwait airways reservations at Aspire Systems
I am an Application engineer in the network chef company. In my free time, I enjoy reading programming and technology ...