Ta sẽ xử lý bài toán này offline. Cụ thể, trước tiên ta sắp xếp lại các giá trị $k$ trong các truy vấn theo chiều tăng dần. Để ý rằng $k$ càng lớn, trong mảng $A$ càng có nhiều số không vượt quá $k$.
Vậy, thuật toán của ta sẽ bao gồm các bước sau:
1. Xét giá trị $k$ trong truy vấn hiện tại. Đánh dấu tất cả các số $\le k$ trong một mảng $mark$ (có giá trị $0/1$) mà chưa được đánh dấu từ một truy vấn trước đó (do ta xử lý offline).
2. Tìm dãy con liên tiếp dài nhất của mảng $mark$ gồm toàn giá trị $1$.
Ý thứ 2 là một ứng dụng phổ biến của cấu trúc DSU. Cụ thể, giả sử ta thêm giá trị thứ $i$ của $A$ trong truy vấn hiện tại, ta xét hai phần tử liền kề với nó:
+ Nếu $i>1$ và $mark[i-1]=1$, ta gộp hai tập hợp chứa phần tử thứ $i$ và $i-1$.
+ Nếu $i<n$ và $mark[i+1]=1$, ta gộp hai tập hợp chứa phần tử thứ $i$ và $i+1$.
Kết quả với từng truy vấn là kích thước của tập hợp lớn nhất trong DSU.
Code mẫu:
```cpp
#include <bits/stdc++.h>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mxn = 1e5 + 3;
int n, q, a[mxn];
int par[mxn], sz[mxn];
bool mark[mxn];
int res = 0; // trước khi xử lý truy vấn nào thì chưa có phần tử nào được đánh dấu nên ta khởi tạo đáp án bằng 0
int find(int u){
return par[u] == u ? u : par[u] = find(par[u]);
}
void join(int u, int v){
u = find(u), v = find(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u, sz[u] += sz[v];
res = max(res, sz[u]); // cập nhật đáp án
}
void solve(){
cin >> n >> q;
vector<pair<int, int>> op, queries;
for (int i = 1; i <= n; ++i){
par[i] = i, sz[i] = 1; // khởi tạo DSU
cin >> a[i];
op.push_back({a[i], i});
}
for (int i = 1, x; i <= q; ++i){
cin >> x;
queries.push_back({x, i});
}
sort(all(op));
sort(all(queries));
vector<int> ans(q);
int id = 0;
for (auto it : queries){
int k = it.first;
while(id < n && op[id].first <= k){
mark[op[id].second] = true;
if (res == 0) res = 1; // đã có ít nhất một phần tử được đánh dấu, vậy nên ta nên cập nhật ngay đáp án lúc này
if (op[id].second > 1 && mark[op[id].second - 1])
join(op[id].second, op[id].second - 1);
if (op[id].second < n && mark[op[id].second + 1])
join(op[id].second, op[id].second + 1);
++id;
}
ans[it.second - 1] = res;
}
for (int i : ans)
cout << i << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
```
tuongll
Created at
35 likes