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;
}
```
Để giải quyết bài toán, ta sẽ sort lại các truy vấn cũng như các phần tử trong mảng a và lưu lại vị trí của chúng, khi duyệt
qua từng truy vấn, ta sẽ hai con trỏ để tìm phần tử a có giá trị bé hơn gần nhất truy vấn với giá trị của truy vấn, ta sẽ kiểm
tra nếu hai bên của phần tử hiện tại trong mảng ban đầu cũng bé hơn giá trị truy vấn hiện tại thì ta sẽ nối chúng vào chung
thành phần liên thông với phần tử a hiện tại đang xét, ta chỉ cần xem max của từng phần tử a đã duyệt qua thì sẽ có được
kết quả của từng truy vấn.
Code mẫu:
```
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<ll,ll> p64;
typedef vector<ll> v64;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, q, ans[N], b[N];
p64 a[N], query[N];
struct DSU{
v64 lab;
DSU(int n): lab(n + 1, -1){}
int find_set(int u){
return lab[u] < 0 ? u : lab[u] = find_set(lab[u]);
}
bool union_set(int u, int v){
u = find_set(u);
v = find_set(v);
if (u == v) return 0;
if (lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return 1;
}
int siz(int u){
return -lab[find_set(u)];
}
};
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i){
cin >> a[i].fi;
b[i] = a[i].fi;
a[i].se = i;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= q; ++i){
cin >> query[i].fi;
query[i].se = i;
}
sort(query + 1, query + 1 + q);
int cur = 1;
int res = 0;
DSU dsu(n);
for (int i = 1; i <= q; ++i){
while (cur <= n && a[cur].fi <= query[i].fi){
if (a[cur].se < n && b[a[cur].se + 1] <= query[i].fi){
dsu.union_set(a[cur].se, a[cur].se + 1);
res = max(res, dsu.siz(a[cur].se));
}
if (a[cur].se > 1 && b[a[cur].se - 1] <= query[i].fi){
dsu.union_set(a[cur].se, a[cur].se - 1);
res = max(res, dsu.siz(a[cur].se));
}
res = max(res, dsu.siz(a[cur].se));
++cur;
}
ans[query[i].se] = res;
}
for (int i = 1; i <= q; ++i){
cout << ans[i] << "\n";
}
return 0;
}
```
tuongll
Created at
52 likes
thaibeo123
Created at
1 likes