Solutions of Small range

Select solution language

YugiHacker Created at 3 likes

#### Nhận xét Với các đoạn con cùng kết thúc tại $i$, nếu vị trí $j$ bắt đầu của đoạn càng nhỏ thì hiệu của số lớn nhất và số nhỏ nhất của đoạn $[a_j ... a_i]$ càng tăng. Vì vậy ta có thể sử dụng thuật toán $2$ con trỏ, với biến $j$ là vị trí trái nhất sao cho đoạn $[a_j ... a_i]$ có hiệu của số lớn nhất và số nhỏ nhất không vượt quá $k$. Ở đây sẽ có nhiều cấu trúc dữ liệu để tìm min - max đoạn: Segment tree, sparse table, deque min-max, $2$ priority queue, multiset. Để code đơn giản, mình sẽ sử dụng multiset cho bài tập này. ```cpp #include<bits/stdc++.h> #define maxn 100005 using namespace std; int n, k; int a[maxn]; long long ans = 0; multiset <int> s; int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> k; int j = 1; for (int i=1; i<=n; i++) { cin >> a[i]; s.insert(a[i]); while (*s.rbegin() - *s.begin() > k) { s.erase(s.find(a[j])); j++; } ans += i - j + 1; } cout << ans; } ```

ntannn Created at 0 likes

For subarrays that end at the same index $i$, the smaller the starting position $j$ of the subarray, the larger the difference between the maximum and minimum value of the segment $[a_j ... a_i]$. Therefore, we can use a two-pointer algorithm, where the variable $j$ is the leftmost position such that the difference between the maximum and minimum value in the segment $[a_j ... a_i]$ does not exceed $k$. There are several data structures that can be used here to find the min-max of a segment: Segment tree, sparse table, min-max deque, 2 priority queues, or a multiset. To keep the code simple, we will use a `multiset` for this exercise. ```cpp #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; typedef long long ll; ll n, k, a[N], ans = 0; multiset<ll> s; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> k; int j = 1; for(int i = 1; i <= n; i++) { cin >> a[i]; s.insert(a[i]); while(*s.rbegin() - *s.begin() > k) { s.erase(s.find(a[j])); j++; } ans += i - j + 1; } cout << ans; } ```