Solutions of Yet another problem

Select solution language

Write solution here.

tuongll Created at 46 likes

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; }$