1700 - Sequence
Time Limit : 2 Second
Memory Limit : 256 MB
Submission: 10
Solved: 6
- Description
You are required to maintain a sequence supporting the following two types of operations:
1. Given m and x, you have to modify the mth element to x.
2. Given m and k, you have to output what the mth element was after the kth operation.
- Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line consists of two integers N and M representing the length of sequence and the number of operations. The next line consists of N integers Ai indicating the ith element in the sequence before any operations. Then M lines follow, each line starts with an integer o representing the type of the operation, if o is 1 then two integers m and x follow, if o is 2 then two integers m and k follow.
Limits
· 1 ≤ N, M ≤ 105.
· -109 ≤ Ai ≤ 109.
· 1 ≤ o ≤ 2 for every operation.
· 1 ≤ m ≤ N for every operation.
· -109 ≤ x ≤ 109 for every operation of type 1.
· k is guaranteed to be valid for every operation of type 2.
· 1 ≤ T × (N + M) ≤ 4×105.
- Output
For each test case, first output one line containing “Case #x:”, where x is the test case number.
Then for every operation of type 2, output one line consists of one integer, which is the mth element after the kth operation.
- sample input
-
2 1 4 2 1 1 2 2 1 1 1 1 6 2 1 3 5 6 4 3 0 2 6 2 3 0 1 2 9 2 2 1 2 2 3 1 5 8 2 5 5
- sample output
-
Case #1: 2 6 Case #2: 0 3 9 8
- hint
- source
- Lalatina