Points:
100 (p)
Time limit:
2.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Cho một dãy \(a\) gồm \(N\) số nguyên, được đánh số từ 1 đến \(N\), số thứ \(i\) có giá trị là \(a_i\) ban đầu tất cả các số đều có giá trị bằng 0. Ta có \(Q\) thao tác. Có hai loại thao tác
- Loại 1: Gồm hai số \(i\), \(v\): gán \(a_i = v\)
- Loại 2: Gồm hai số \(l\), \(r\): trả về số có giá trị lớn nhất trong đoạn từ \(l\) đến \(r\).
Input
- Dòng đầu tiền gồm 2 hai số nguyên dương \(N\), \(Q\) (\(N, Q \leq 2000\))
- Dòng thứ hai gồm \(N\) số, là giá trị ban đầu của dãy \(a\)
- \(Q\) dòng tiếp theo mỗi dòng là gồm 3 số, số đầu tiên là \(t\) (\(1 \leq t \leq 2\)), là loại thao tác của thao tác hiện tại. Nếu \(t = 1\), hai số tiếp theo sẽ là \(i\) và \(v\) (\(1 \leq i \leq N\), \(1 \leq v \leq 10^{9}\)). Nếu \(t = 2\), hai số tiếp theo sẽ là \(l\) và \(r\) \((1 \leq l \leq r \leq n)\).
Output
- Dòng nhiều dòng là đáp án cho các thao tác loại 2, mỗi số in trên một dòng.
Example
Test 1
Input
5 6
1 2 3 4 5
2 1 5
1 1 6
2 1 5
2 2 4
1 2 5
2 2 4
Output
5
6
4
5
Comments
code segment tree 1 đống xong nhìn lại thấy N, Q <= 2000 =))