# BÀI TẬP RANGE QUERY

## **1. Đề bài: Range Update Point Query**

Bạn có một mảng $a$ gồm $n$ phần tử ban đầu đều bằng $0$. Bạn cần thực hiện $q$ truy vấn. Mỗi truy vấn thuộc một trong hai loại sau:
1. **Cập nhật đoạn:**
- Bạn được cho $l$ và $r$. Hãy tăng tất cả các phần tử trong đoạn $[l, r]$ lên 1.
2. **Truy vấn điểm:**
- Bạn được cho $x$. Hãy trả về giá trị của $a_x$ (giá trị tại vị trí $x$).

### **Input**
- Dòng đầu tiên chứa hai số nguyên $n$ và $q$ $(1 \leq n, q \leq 10^5)$ — độ dài của mảng và số lượng truy vấn.
- $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn:
- Nếu truy vấn là loại 1, bạn được cho số nguyên $1 \ l \ r$ $(1 \leq l \leq r \leq n)$.
- Nếu truy vấn là loại 2, bạn được cho số nguyên $2 \ x$ $(1 \leq x \leq n)$.

### **Output**
- Với mỗi truy vấn loại 2, in ra giá trị của $a_x$ sau khi thực hiện tất cả các truy vấn trước đó.

---

### **Ví dụ**

#### **Input**

3
5 8
1 420 69 1434 2023
1 2 3
2 2
2 3
2 4
1 2 5
2 1
2 3
2 5
2 3
9999 1000
1 1 2
2 1
2 2
1 6
2 4
2 3
1 1 2
2 1

#### **Output**

6
15
1434
1
6
7
36
1
1

:::spoiler **Ý tưởng**
- $S(n)$ là tổng các chữ số của $n$. Sau 3 lần áp dụng, giá trị $a_i$ sẽ không thay đổi nữa.
- Chỉ cần cập nhật mỗi phần tử tối đa 2 lần.
- Dùng set để lưu các chỉ số còn "hoạt động" (được cập nhật ≤ 2 lần).
- Quy trình:
-- $1\ l\ r$ — Cập nhật các phần tử trong đoạn $[l, r]$ bằng cách thay $a_i$ thành $S(a_i)$.
-- $2\ x$ — Trả về giá trị $a_x$.
- Độ phức tạp $\mathcal{O}(q + n \log n)$.
:::
:::spoiler **Code**

#include <bits/stdc++.h>
using namespace std;

int digit_sum(int n) {
    int ret = 0;
    while(n) {
        ret += n % 10;
        n /= 10;
    }
    return ret;
}
void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    set<int> s;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        if(a[i] > 9) s.insert(i);
    }
    while(q--) {
        int type; cin >> type;
        if(type == 1) {
            int l, r; cin >> l >> r; --l, --r;
            int lst = l;
            while(!s.empty()) {
                auto it = s.lower_bound(lst);
                if(it == s.end() || *it > r) break;
                a[*it] = digit_sum(a[*it]);
                int paiu = *it;
                s.erase(it);
                if(a[paiu] > 9) s.insert(paiu);
                lst = paiu + 1;
            }
        } else {
            int x; cin >> x; --x;
            cout << a[x] << "\n";
        }
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(0);
	int t; cin >> t;
	while(t--) {
	    solve();
	}
}

:::

## **2. Đề bài: Range Xor Queries**

Cho một mảng $a$ gồm $n$ phần tử, nhiệm vụ của bạn là thực hiện $q$ truy vấn có dạng: Tính tổng xor các giá trị nằm trong đoạn từ vị trí $a$ tới vị trí $b$ ?

### **Input**
- Dòng đầu tiên chứa hai số nguyên $n$ và $q$ $(1 \leq n, q \leq 2 \times 10^5)$ — độ dài của mảng và số lượng truy vấn.
- Dòng thứ hai chứa $n$ số nguyên $x_1, x_2, ..., x_n$ - Giá trị của từng phần tử trong mảng $a$ $(1 \leq x_i \leq 10^9)$.
- $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn bao gồm 2 số nguyên $a$ và $b$ - Tổng xor của các giá trị trong đoạn từ vị trí $a$ của mảng đến vị trí $b$ ? $(1 \leq a \leq b \leq n)$

### **Output**
- In ra kết quả của mỗi truy vấn.

---

### **Ví dụ**

#### **Input**

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

#### **Output**

3
0
6
4

:::spoiler **Ý tưởng**
- Ý tưởng chính:
- Mỗi khi gặp bài toán truy vấn trên một đoạn (range queries), chúng ta thường nghĩ ngay đến việc sử dụng mảng tiền tố (prefix sums). Tuy nhiên, vì ở đây chúng ta đang làm việc với phép XOR trên một đoạn, nên ta sẽ dùng mảng tiền tố XOR thay vì mảng tiền tố cộng thông thường. Cách làm là định nghĩa một mảng **prefix** sao cho:
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ prefix[a - 1] \ = \ arr[1] \ \oplus \ arr[2] \ \oplus \ ... \oplus \ arr[a - 1]$
- Do đó, với mỗi truy vấn $(a, b)$, kết quả sẽ là:
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ prefix[a - 1] \ \oplus \ prefix[b]$
- Chứng minh:
- Ta biết: $prefix[a - 1] \ = \ arr[1] \ \oplus \ arr[2] \ \oplus ... \oplus \ arr[a - 1]$
- Và: $prefix[b] \ = \ arr[1] \ \oplus \ arr[2] \ \oplus ... \oplus \ arr[b]$
- Vì tính chất $x \ \oplus \ x \ = \ 0$ với mọi $x$, nên:
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ prefix[a - 1] \ \oplus \ prefix[b]$
$\ \ \ \ \ = \ (arr[1] \ \oplus ... \oplus \ arr[a - 1]) \ \oplus \ (arr[1] \ \oplus ... \oplus \ arr[b])$
$\ \ \ \ \ \ \ \ \ \ = \ arr[a] \ \oplus \ arr[a + 1 ] \oplus \ ... \ \oplus \ arr[b]$
:::
:::spoiler **Code**

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5;

int n, q, arr[MAX_N + 1], prefix[MAX_N + 1], a, b;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> q;
	// arr and prefix use 1-based indexing
	for (int i = 1; i <= n; ++i) { cin >> arr[i]; }
	// Build prefix XOR array
	prefix[1] = arr[1];
	for (int i = 2; i <= n; i++) { prefix[i] = prefix[i - 1] ^ arr[i]; }

	while (q--) {
		cin >> a >> b;
		cout << (prefix[a - 1] ^ prefix[b]) << endl;
	}
}

:::

## **3. Đề bài: Little Elephant and Array**

- Bạn có một mảng gồm **n** số nguyên dương $a_1, a_2, \dots, a_n$. Một số nguyên được gọi là **đặc biệt** nếu tổng các chữ số của nó xuất hiện trong mảng nhiều hơn hoặc bằng chính nó.

- Cho **q** truy vấn, mỗi truy vấn yêu cầu đếm số lượng số **đặc biệt** trong đoạn từ **l** đến **r**.

### **Input**
- Dòng đầu tiên chứa hai số nguyên **n** và **q** $(1 \leq n, q \leq 10^5)$.
- Dòng thứ hai chứa **n** số nguyên dương $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq 10^6)$.
- Mỗi dòng tiếp theo chứa hai số nguyên **l** và **r** $(1 \leq l \leq r \leq n)$ đại diện cho một truy vấn.

### **Output**
- Với mỗi truy vấn, in ra số lượng số **đặc biệt** trong đoạn từ **l** đến **r**.

### Ví dụ
#### **Input**

7 2
3 1 2 2 3 3 7
1 7
3 4

#### **Output**

3
1

:::spoiler **Ý tưởng**
- Có thể giải bài này bằng cách **$\\{O}(N\\sqrt{N})$**, nhưng lời giải được mô tả ở đây là **$\\{O}(N\\log N)$**.
- Giải bài toán bằng cách xử lý offline.
- Duyệt qua các giá trị **x** từ **0** đến **n − 1**.
- Sử dụng mảng **D** để tính kết quả cho các truy vấn kết thúc tại **x**.
- Để cập nhật **D**, giữ danh sách các vị trí xuất hiện trước đó của số **t** và xử lý để đảm bảo chính xác số lượng.
:::
:::spoiler **Code**

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
 
const int N=1e5+5;
 
vector<int> v;
int a[N],cn[N],p[505][N];
 
void solve()
{
    int n,q,c=0;
    cin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        if(a[i]<=n) cn[a[i]]++;
    }
    for(int x=1;x<=n;x++) if(cn[x]>=x)
    {
        v.push_back(x);
        for(int i=1;i<=n;i++) p[c][i]=p[c][i-1]+(a[i]==x);
        c++;
    }
    while(q--)
    {
        int l,r,ans=0;cin >> l >> r;
        for(int i=0;i<c;i++) ans+=(p[i][r]-p[i][l-1]==v[i]);
        cout << ans << endl;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

:::

## **4. Đề bài: Dynamic Range Minimum Querries**

Cho một mảng $a$ gồm $n$ phần tử, nhiệm vụ của bạn là thực hiện $q$ truy vấn thuộc hai loại sau đây:
1. **Cập nhật**: Cập nhật giá trị tại vị trí $k$ thành $u$.
2. **Truy cập**: Tìm giá trị nhỏ nhất trong đoạn $[a, b]$ ?

### **Input**
- Dòng đầu tiên chứa hai số nguyên $n$ và $q$ $(1 \leq n, q \leq 2 \times 10^5)$ — độ dài của mảng và số lượng truy vấn.
- Dòng thứ hai chứa $n$ số nguyên $x_1, x_2, ..., x_n$ - Giá trị của từng phần tử trong mảng $a$ $(1 \leq x_i \leq 10^9)$.
- $q$ dòng tiếp theo, mỗi truy vấn chứa 3 số nguyên : "$1 \ k \ u$" hoặc "$2 \ a \ b$".

### **Output**
- In ra kết quả của mỗi truy vấn loại $2$.

---

### **Ví dụ**

#### **Input**

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

#### **Output**

2
1
1
4

:::spoiler **Ý tưởng**
- Ý tưởng chính: Áp dụng **Segment Tree** để xử lý
- Đầu tiên, ta sẽ xây dựng **Segment Tree** trên mảng $n$ phần tử.
- Mỗi **node** trong cây sẽ lưu giá trị nhỏ nhất (min) trên đoạn nó xử lý.
- Khi có truy vấn:
- **Update** (cập nhật) giá trị tại vị trí $k$: ta cập nhật trên Segment Tree để giá trị min trong các node liên quan cũng được thay đổi tương ứng.
- **Query** (lấy min) trên đoạn $[a, b]$: ta duyệt cây để tổng hợp kết quả từ các node nằm trong đoạn $[a, b]$.
:::
:::spoiler **Code**

#include <bits/stdc++.h>
using namespace std;

const long long INF = LLONG_MAX;

vector<long long> arr;  // mảng gốc (1-based)
vector<long long> seg;  // Segment Tree (lưu giá trị min)

// Xây dựng Segment Tree
void build(int idx, int start, int end) {
    if (start == end) {
        // node lá, lưu giá trị arr[start]
        seg[idx] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(idx * 2, start, mid);
    build(idx * 2 + 1, mid + 1, end);
    seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
}

// Cập nhật giá trị tại vị trí pos = val
void update(int idx, int start, int end, int pos, long long val) {
    if (start == end) {
        // node lá tương ứng với vị trí pos
        seg[idx] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (pos <= mid) {
        update(idx * 2, start, mid, pos, val);
    } else {
        update(idx * 2 + 1, mid + 1, end, pos, val);
    }
    seg[idx] = min(seg[idx * 2], seg[idx * 2 + 1]);
}

// Truy vấn giá trị min trên đoạn [L, R]
long long queryMin(int idx, int start, int end, int L, int R) {
    // Nếu [start, end] nằm ngoài [L, R], trả về giá trị "vô hại"
    if (R < start || end < L) {
        return INF;
    }
    // Nếu [start, end] nằm hoàn toàn trong [L, R], trả về seg[idx]
    if (L <= start && end <= R) {
        return seg[idx];
    }
    // Truy vấn 2 nhánh trái - phải
    int mid = (start + end) / 2;
    long long leftMin = queryMin(idx * 2, start, mid, L, R);
    long long rightMin = queryMin(idx * 2 + 1, mid + 1, end, L, R);
    return min(leftMin, rightMin);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    
    arr.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    // Segment Tree thường cần mảng kích thước 4*n
    seg.resize(4 * (n + 1), 0);

    // Xây dựng cây
    build(1, 1, n);

    // Xử lý q truy vấn
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            // Cập nhật: 1 k u
            int k;
            long long u;
            cin >> k >> u;
            update(1, 1, n, k, u);
        } else {
            // Truy vấn min: 2 a b
            int a, b;
            cin >> a >> b;
            cout << queryMin(1, 1, n, a, b) << "\n";
        }
    }

    return 0;
}

:::