VOJ - KQUERY2
Source: KQUERY2
Tags: Data Structures, Sqrt - Decomposition
Problem:
Cho một dãy N phần tử A[1], A[2], ..., A[N] và một số các truy vấn-k. Ngoài ra còn có một số thao tác cập nhật.
Một thao tác cập nhật (i, v) nghĩa là A[i] cần được gán giá trị v.
Một truy vấn-k là một bộ ba (i, j, k), với mỗi truy vấn-k, bạn cần trả về số phần tử lớn hơn k nằm trong dãy con A[i], A[i + 1], ..., A[j].
1 ≤ N ≤ 3e4.
1 ≤ A[i] ≤ 1e4.
1 ≤ Q ≤ 2e5. Q là số lượng các thao tác cập nhật và các truy vấn-k.
Q dòng tiếp theo, số đầu tiên là 0 hoặc 1:
- 0 cho biết đó là thao tác cập nhật, theo sau là 2 số i, v (1 ≤ i ≤ N, 1 ≤ v ≤ 1e4).
- 1 cho biết đó là truy vấn-k, theo sau là 3 số i, j, k (1 ≤ i ≤ j ≤ N, 1 ≤ 1e4 ≤ k).
Ví dụ:
Input:
5
5 1 2 3 4
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2
Output:
2
1
2
Explanation:
Mảng ban đầu
5 1 2 3 4
Truy vấn-k (2, 4, 1)
→ Có 2 số lớn hơn 1 là 2, 3.
Mảng sau khi cập nhật (4, 10)
5 1 2 10 4
Truy vấn-k (4, 4, 4)
→ Có 1 số lớn hơn 4 là 10.
Mảng sau khi cập nhật (3, 1)
5 1 1 10 4
Mảng sau khi cập nhật (1, 2)
2 1 1 10 4
Truy vấn-k (1, 5, 2)
→ Có 2 số lớn hơn 2 là 10, 4.
Solution:
Tags: Data Structures, Sqrt - Decomposition
Problem:
Cho một dãy N phần tử A[1], A[2], ..., A[N] và một số các truy vấn-k. Ngoài ra còn có một số thao tác cập nhật.
Một thao tác cập nhật (i, v) nghĩa là A[i] cần được gán giá trị v.
Một truy vấn-k là một bộ ba (i, j, k), với mỗi truy vấn-k, bạn cần trả về số phần tử lớn hơn k nằm trong dãy con A[i], A[i + 1], ..., A[j].
1 ≤ N ≤ 3e4.
1 ≤ A[i] ≤ 1e4.
1 ≤ Q ≤ 2e5. Q là số lượng các thao tác cập nhật và các truy vấn-k.
Q dòng tiếp theo, số đầu tiên là 0 hoặc 1:
- 0 cho biết đó là thao tác cập nhật, theo sau là 2 số i, v (1 ≤ i ≤ N, 1 ≤ v ≤ 1e4).
- 1 cho biết đó là truy vấn-k, theo sau là 3 số i, j, k (1 ≤ i ≤ j ≤ N, 1 ≤ 1e4 ≤ k).
Ví dụ:
Input:
5
5 1 2 3 4
6
1 2 4 1
0 4 10
1 4 4 4
0 3 1
0 1 2
1 1 5 2
Output:
2
1
2
Explanation:
Mảng ban đầu
5 1 2 3 4
Truy vấn-k (2, 4, 1)
→ Có 2 số lớn hơn 1 là 2, 3.
Mảng sau khi cập nhật (4, 10)
5 1 2 10 4
Truy vấn-k (4, 4, 4)
→ Có 1 số lớn hơn 4 là 10.
Mảng sau khi cập nhật (3, 1)
5 1 1 10 4
Mảng sau khi cập nhật (1, 2)
2 1 1 10 4
Truy vấn-k (1, 5, 2)
→ Có 2 số lớn hơn 2 là 10, 4.
Solution:
Để giải quyết bài này, đầu tiên ta cần chia dãy N số ra thành căn N đoạn. Đặt M = căn N, ta có N / M đoạn mỗi đoạn có độ dài M, nếu N không chia hết cho M, ta sẽ có thêm một đoạn N / M + 1 nữa độ dài N % M. Sau đó ta dựng N / M cây BIT, BIT[i][x] quản lý tổng số lượng phần tử từ đoạn 1 đến đoạn i lớn hơn hoặc bằng x.
Mỗi lần cập nhật cần -1 vào cây BIT[x][A[i]], trong đó x là đoạn chứa phần tử i, và +1 vào cây BIT[x][v]. Thao tác cập nhật sẽ là O(sqrt(N) * log(1e4)), trong trường hợp xấu nhất sẽ cập nhật BIT[N / M][1], duyệt qua N / M đoạn và duyệt cây BIT trong log(1e4).
Với mỗi truy vấn-k, nếu i và j thuộc cùng một đoạn, ta chỉ việc duyệt từ i đến j và đếm thôi. Nếu i và j khác đoạn, ta tiến hành duyệt từ i đến cuối đoạn chứa i đếm và duyệt từ j về đầu đoạn chứa j đếm, gọi l là đoạn sau i và r là đoạn trước j, sau đó ta lấy giá trị BIT[l - 1][k + 1] và BIT[r][k + 1] trong log(1e4 - k - 1) để tính BIT[r][k + 1] - BIT[l - 1][k + 1], đây là tổng các đoạn từ l đến r. Tổng các kết quả là đáp án. Mỗi truy vấn thực hiện trong O(sqrt(N) + log(1e4)).
Tổng độ phức tạp O(Q * sqrt(N) * log(1e4)).
Thực ra độ phức tạp này vẫn khá nguy hiểm vì Q của đề bài đến tận 2e5, max sqrt(N) = 173 và log(1e4) = 13, tính ra vẫn có thể TLE, ta có thể nâng cấp thao tác update bằng cách dựng cây BIT 2D, tức là một cây BIT quản lý các đoạn từ 1 đến N / M, mỗi nút của nó là một cây BIT quản lý số lượng các giá trị như trên. Như vậy thao tác update sẽ giảm xuống còn O(log(sqrt(N)) * log(1e4)), lúc này chắc chắn sẽ không TLE nữa.
Tuy nhiên cách cài trên tương đối rắc rối, sqrt(N) đã tương đối nhỏ và trên thực tế thì cách chưa tối ưu mình nộp lên vẫn AC, do đó bạn có thể code BIT 2D như là một bài tập thêm :D
Code: (chưa tối ưu) //note: trong code dưới, mảng sum là cây BIT
#include <iostream>
using namespace std;
int n, q, a[30015], sum[10001][200];
#define id(x) (x / 200 + (x % 200 > 0))
void update(int k, int x, int v) {
for (x = id(x); x <= id(n); x++)
for (int i = k; i; i -= i & -i)
sum[i][x] += v;
}
int get(int k, int l, int r) {
int cnt = 0;
if (id(l) == id(r))
for (int i = l; i <= r; i++)
cnt += a[i] > k;
else {
for (int x = id(l); id(l) == x; l++)
cnt += a[l] > k;
for (int x = id(r); id(r) == x; r--)
cnt += a[r] > k;
if (id(l) <= id(r)) {
for (int i = k + 1; i <= 1e4; i += i & -i)
cnt += sum[i][id(r)];
for (int i = k + 1; i <= 1e4; i += i & -i)
cnt -= sum[i][id(l) - 1];
}
}
return cnt;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], update(a[i], i, 1);
cin >> q;
for (int t, x, y, k; q--;) {
cin >> t >> x >> y;
if (t)
cin >> k,
cout << get(k, x, y) << '\n';
else
update(a[x], x, -1),
update(y, x, 1),
a[x] = y;
}
}
Code: (đã tối ưu bằng BIT 2D, hmmm thật ra sau khi nghĩ lại thì mình thấy nó cũng không rắc rối hơn là bao, chỉ quan trọng là bản thân người code đủ kinh nghiệm để nghĩ nhanh hay không thôi :D)
#include <iostream>
using namespace std;
int n, q, a[30015], sum[10001][200];
#define id(x) (x / 200 + (x % 200 > 0))
void update(int k, int x, int v) {
for (x = id(x); x <= id(n); x += x & -x)
for (int i = k; i; i -= i & -i)
sum[i][x] += v;
}
int get(int k, int l, int r) {
int cnt = 0;
if (id(l) == id(r))
for (int i = l; i <= r; i++)
cnt += a[i] > k;
else {
for (int x = id(l); id(l) == x; l++)
cnt += a[l] > k;
for (int x = id(r); id(r) == x; r--)
cnt += a[r] > k;
if (id(l) <= id(r)) {
for (int x = id(r); x; x -= x & -x)
for (int i = k + 1; i <= 1e4; i += i & -i)
cnt += sum[i][x];
for (int x = id(l) - 1; x; x -= x & -x)
for (int i = k + 1; i <= 1e4; i += i & -i)
cnt -= sum[i][x];
}
}
return cnt;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], update(a[i], i, 1);
cin >> q;
for (int t, x, y, k; q--;) {
cin >> t >> x >> y;
if (t)
cin >> k,
cout << get(k, x, y) << '\n';
else
update(a[x], x, -1),
update(y, x, 1),
a[x] = y;
}
}
Nhận xét
Đăng nhận xét