Fast Arrays

0

0 votes
Problem

Mike is looking for long flat strips of land to use for creating an obstacle race course. Once he finds a strip of land, he splits it into L sections (numbered 0 to L-1) and notes down the elevation E of the land. Then he goes about designing the land. To design, he needs to be able to get the elevation of a section of the land and to be able to set the elevation of a section of the land. But since the land could be big, he wants it done fast so he comes to you. For each of his queries, return the elevation of the section of land that he wants.

Input format:
First line contains the number of test cases t.
In each test case, the first line contains two numbers L and E.
The second line contains the number of queries q.
The next q lines are of the form "0 <section number>" or "1 <section number> <new value>"

Output format:
For each query of the form "0 <section number>", output the elevation of that section on a single line. For every query of the form "1 <section number> <new_value> update the section with the new_value

Sample Input:
3
10 55
5
0 5
1 5 20
0 5
1 5 0
0 5
1000 29
4
1 13 21
1 15 10
0 13
0 12
1000000 12345678
3
1 0 13
0 1
0 0

Sample Output:
55
20
0
21
29
12345678
13

Limits:
L <= 10^6
E (and any other elevation) fits in an int
t <= 10
q <= 2*10^6

Time Limit: 3
Memory Limit: 25
Source Limit:
Editor Image

?