# Hướng Dẫn
## Mô tả bài toán
Cho một mảng A gồm các phần tử nguyên với độ dài n và có q truy vấn. Mỗi truy vấn có dạng i, x, yêu cầu chèn giá trị x vào vị trí i của mảng A. Sau mỗi truy vấn, in ra mảng A.
## Giải thuật
1. **Khởi tạo mảng**: Đọc số nguyên `n` và `q` từ đầu vào. Tạo một mảng `A` với `n` phần tử từ đầu vào.
2. **Thực hiện các truy vấn**:
- Đọc số nguyên `i` và `x` từ đầu vào.
- Chèn giá trị `x` vào vị trí `i` của mảng `A`.
- In ra mảng `A` sau khi chèn.
## Độ phức tạp
- Độ phức tạp thời gian của thuật toán là `O(n + q * m)`, trong đó `m` là kích thước trung bình của mảng sau mỗi truy vấn. Điều này là do việc chèn vào vector có độ phức tạp trung bình là `O(m)`.
## Code
```cpp
/*
author: longvuu
github: kuronight29
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
ll n, q;
cin >> n >> q;
vector<ll> A;
for (ll i = 0; i < n; i++)
{
ll x;
cin >> x;
A.push_back(x);
}
for (ll i = 0; i < q; i++)
{
ll x, y;
cin >> x >> y;
A.insert(A.begin() + x-1, y);
for (ll j = 0; j < A.size(); j++)
{
cout << A[j] << " ";
}
cout << endl;
}
}
```
# Hướng Dẫn
## Mô tả bài toán
Cho một mảng `A` gồm các phần tử nguyên với độ dài `n` và có `q` truy vấn. Mỗi truy vấn có dạng `i`, `x`, yêu cầu chèn giá trị `x` vào vị trí `i` của mảng `A`. Sau mỗi truy vấn, in ra mảng `A`. Do mảng là cấu trúc tĩnh và không hỗ trợ trực tiếp chèn phần tử giữa các vị trí, ta sử dụng danh sách liên kết đơn (linked list) để thực hiện bài toán hiệu quả hơn, đặc biệt với các thao tác chèn.
## Cấu trúc dữ liệu
1. Danh sách liên kết đơn (Singly Linked List):
- Mỗi nút trong danh sách bao gồm:
- Dữ liệu (`data`): Lưu giá trị của phần tử.
- Con trỏ (`next`): Trỏ đến nút tiếp theo trong danh sách.
- Danh sách được quản lý bởi: Con trỏ đầu (`head`): Trỏ đến nút đầu tiên.
2. Các thao tác chính:
- Chèn đầu: Chèn giá trị `x` vào đầu danh sách.
- Chèn cuối: Chèn giá trị `x` vào cuối danh sách.
- Chèn tại vị trí `i`: Chèn giá trị `x` vào vị trí `i`.
- Nếu `i` = 1, chèn đầu danh sách.
- Nếu `i` > số phần tử, chèn cuối danh sách.
- Các trường hợp còn lại, duyệt danh sách đến vị trí trước `i` và chèn.
## Mô tả giải thuật
1. Khởi tạo danh sách liên kết đơn:
- Đọc số nguyên `n` và `q`.
- Tạo danh sách liên kết và thêm lần lượt `n` phần tử vào cuối bằng `addTail`.
2. Xử lý `q` truy vấn:
Mỗi truy vấn có dạng `i`, `x`:
- Gọi hàm `insertAtIdx` để chèn giá trị `x` tại vị trí `i`.
- Sử dụng vòng lặp để duyệt đến vị trí `i` - 1 trong danh sách và thực hiện chèn.
3. In danh sách sau mỗi truy vấn:
Duyệt toàn bộ danh sách từ head đến `nullptr` và in giá trị từng nút.
## Đánh giá độ phức tạp
1. Thời gian:
- [x] Duyệt danh sách để chèn tại vị trí `i`: O(n).
- [x] Với `q` truy vấn: O(q * n).
2. Không gian: Bộ nhớ danh sách liên kết động: O(n + q).
# Code
```
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Node {
ll data;
Node* pNext;
Node(ll val) : data(val), pNext(nullptr) {}
};
struct List {
Node* pHead;
List() : pHead(nullptr) {}
};
void addHead(List &L, ll val) {
Node *new_node = new Node(val);
new_node->pNext = L.pHead;
L.pHead = new_node;
}
void addTail(List &L, ll val) {
Node *new_node = new Node(val);
if (!L.pHead) {
L.pHead = new_node;
return;
}
Node *curr = L.pHead;
while (curr->pNext) {
curr = curr->pNext;
}
curr->pNext = new_node;
}
void insertAtIdx(List &L, ll idx, ll val) {
if (idx == 1) {
addHead(L, val);
return;
}
Node *curr = L.pHead;
Node *new_node = new Node(val);
idx--;
while (idx > 1 && curr) {
curr = curr->pNext;
idx--;
}
if (!curr) {
cout << "Index out of range.\n";
delete new_node;
return;
}
new_node->pNext = curr->pNext;
curr->pNext = new_node;
}
void printList(List &L) {
Node *curr = L.pHead;
while (curr) {
cout << curr->data << " ";
curr = curr->pNext;
}
cout << endl;
}
int main() {
ll n, q;
cin >> n >> q;
List L;
for (ll i = 0; i < n; i++) {
ll x;
cin >> x;
addTail(L, x);
}
for (ll i = 0; i < q; i++) {
ll x, y;
cin >> x >> y;
insertAtIdx(L, x, y);
printList(L);
}
return 0;
}
```
### @github/support [bienbeo](https://github.com/Bien-Beo)
longvuuu
Created at
1 likes
bienbeo
Created at
0 likes