Cấu trúc dữ liệu dạng Cây (Segment Tree)

Cho 1 dãy \(n\) số nguyên, nhiệm vụ của bạn là hãy xử lí \(q\) truy vấn dưới dạng: tính tổng xor của các giá trị trong khoảng [\(a\),\(b\)].

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\): số lượng giá trị của dãy và truy vấn
• Dòng thứ hai gồm \(n\) số nguyên \(x_1, x_2,...,x_n\): giá trị dãy số
• Cuối cùng, có \(q\) dòng truy vấn. Mỗi dòng gồm 2 số nguyên \(a\) và \(b\): tính tổng xor của các giá trị trong khoảng [\(a\),\(b\)]

Constraints

• \(1 \leq n,q \leq 2\cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)
• \(1 \leq a \leq b \leq n\)

Output

• In ra kết quả của các truy vấn loại 2

Example

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

3
0
6
4

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p_i\) \(x_i\): Tăng phần tử ở vị trí \(p_i\) lên \(x_i\) đơn vị.
• \(2\) \(u_i\) \(v_i\): Tính tổng các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu
Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\) và \(x_i\) \((1 \leq p_i \leq N\), \(1 \leq x_i \leq 10^4)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần atử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

6 5
9 2 4 7 4 8
1 5 6
2 1 5
1 3 8
1 2 3
2 2 4 

32
24

Cho dãy \(a\) gồm \(n\) phần tử là các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\). Cho \(q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(u_{i}\) \(v_{i}\) \(x_{i}\): Tăng mỗi phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\) lên \(x_{i}\) đơn vị.
• \(2\) \(u_{i}\) \(v_{i}\): Tính tổng các phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\).

Yêu cầu: thực hiện tất cả lần lượt \(q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n, q\) \((1 \leq n, q \leq 10^{5})\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_{i}\), \(v_{i}\) và \(x_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n, 1 \leq x_{i} \leq 10^{9})\). Số \(2\) theo sau bởi hai số nguyên dương \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần tử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): mọi thao tác loại \(1\) có \(u = v\).
• Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

5 4
1 4 6 2 3
2 1 4
1 2 5 3
1 3 4 5
2 3 5 

13
30

Cho mảng gồm \(N\) phần tử là các số nguyên. Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• \(1\) \(a\) \(b\) \(x\) : Tăng các phần tử từ \(a\) đến \(b\) lên \(x\).
• \(2\) \(a\) \(b\) \(x\) : Thay đổi tất cả các phần tử từ \(a\) đến \(b\) thành \(x\).
• \(3\) \(a\) \(b\) : Tính tổng các phần tử từ \(a\) đến \(b\).

Input

• Dòng thứ nhất gồm hai số nguyên \(N, Q\) là kích thước mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^6)\).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong ba dạng sau:
  • \(1\) \(a\) \(b\) \(x\) \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).
  • \(2\) \(a\) \(b\) \(x\) \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).
  • \(3\) \(a\) \(b\) \((1 \leq a \leq b \leq N)\).

Output

• In ra kết quả cho các truy vấn \(3\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 2.10^5\).

Example

6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5 

7
11
15

Cho dãy số \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\), và \(Q\) truy vấn, truy vấn thứ \(i\) gồm \(2\) số nguyên dương \(L_i, R_i\) \((1 \leq L_i \leq R_i \leq N)\).

Yêu cầu: Với mỗi truy vấn thứ \(i\), hãy đếm số phần tử phân biệt trong khoảng từ \(L_i\) tới \(R_i\).

Input

• Gồm \(Q+2\) dòng:
• Dòng thứ nhất chứa hai số nguyên dương \(N, Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^6)\).
• \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(L_i, R_i\).

Output

• In ra \(Q\) dòng, dòng thứ \(i\) là số phần tử phân biệt trong khoảng từ \(L_i\) tới \(R_i\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 10^5\).

Example

5 3
1 1 2 1 3
1 5
2 4
3 5 

3
2
3

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(u_i\) \(v_i\) \(x_i\): Tăng mỗi phần tử từ vị trí \(u_i\) tới vị trí \(v_i\) lên \(x_i\) đơn vị.
• \(2\) \(u_i\) \(v_i\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu: Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_i\), \(v_i\) và \(x_i\) \((1 \leq u_i \leq v_i \leq N\), \(1 \leq x_i \leq 10^9)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), chỉ có các thao tác loại \(2\).
• Subtask \(3\) (\(20\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), các thao tác \(1\) luôn được thực hiện trước các thao tác \(2\).
• Subtask \(4\) (\(30\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

5 4
2 6 3 5 8
1 2 5 3
2 1 4
1 3 4 2
2 3 5 

9
11

Cho dãy \(a\) gồm \(n\) phần tử là các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{N}\). Cho \(q\) thao tác thực liện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p\) \(x\): Chèn giá trị \(x\) vào giữa hai vị trí \(p - 1\) và \(p\) trong dãy \(a\) \((1 \leq p \leq t + 1\), với \(t\) là số phần tử hiện có trong dãy \(a\). Nếu \(p = t + 1\), chèn \(x\) vào cuối dãy \(a\).
• \(2\) \(u\) \(v\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\) \((1 \leq u \leq v \leq t\), với \(t\) là số phần tử hiện có trong dãy \(a).\)

Yêu cầu: Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n, q\) \((1 \leq n, q \leq 10^{5})\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{N}\) \((a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo, mỗi dòng thể hiện 1 truy vấn thuộc 1 trong 2 loại:/
  • \(1\) \(p\) \(x\) \((1 \leq p \leq n, 1 \leq x \leq 10^{9})\).
  • \(2\) \(u\) và \(v\) \((1 \leq u \leq v \leq n)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): các thao tác \(1\) luôn được thực hiện trước các thao tác \(2\).
• Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

3 4
2 3 1
1 3 2
2 2 3
1 3 5
2 1 4 

3
5