## MSecond - Editorial
### Subtask 1
Xét từng đoạn $[l,r]$ bằng cách cố định $r$, sau đó $for$ ngược $l$ về, ta duy trì việc tìm $MaxSecond$ và $MinSecond$ mỗi lần $l$ thay đổi.
Độ phức tạp: $O(n^2)$.
### Subtask 2
Ta nhận thấy rằng, nếu có đoạn độ dài $x$ thỏa mãn, thì đoạn độ dài $x-1$ cũng sẽ thỏa mãn.
Do đó ta sẽ tìm kiếm nhị phân kết quả.
Để kiểm tra có đoạn độ dài $x$ nào thỏa mãn hay không, ta làm như sau:
- Chuẩn bị một ```multiset<int> s```.
- Ta cho hết các phần tử trong đoạn $[1,x]$ vào $s$. Ta có thể lấy giá trị $MinSecond$ và $MaxSecond$ từ $s$ trong $O(log)$.
- Để chuyển lên kiểm tra đoạn $[2,x+1]$, ta chỉ cần xóa phần tử $a_1$ đi và thêm phần tử $a_{x+1}$ vào.
- Như vậy, giả sử ta đang kiểm tra đoạn $[l,l+x-1]$, khi cần chuyển lên đoạn $[l+1,l+x]$, ta sẽ xóa phần tử $a_l$ đi và thêm $a_{l+x}$ vào $s$.
- Vậy để kiểm tra tất cả các đoạn ta chỉ cần xóa và thêm $2*n$ lần vào $s$.
- Lưu ý, khi xóa một phần tử $x$ ra khỏi $s$ cần dùng lệnh ```s.erase(s.find(x))```, nếu dùng ```s.erase(x)``` thì sẽ xóa tất cả các phần tử bằng $x$ trong $s$.
Độ phức tạp: $O(n*log^2)$.
<details>
<summary>Nhấn để xem code</summary>
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,k;
int a[N];
bool check (int mid) {
multiset<int> s;
for (int i=1; i<=n; i++) {
s.insert(a[i]);
if (s.size() < mid) {
continue;
}
auto it = s.begin(); it++;
int Min = *it;
auto it2 = s.rbegin(); it2++;
int MaxSecond = *it2;
if (MaxSecond - Min <= k) return true;
s.erase(s.lower_bound(a[i-mid+1]));
}
return false;
}
namespace trau {
pair<int,int> sec (int l, int r) {
vector<int> v;
for (int i=l; i<=r; i++) v.push_back(a[i]);
sort(v.begin(),v.end());
return pair<int,int> (v[1],v[r-l-1]);
}
void solve () {
int res = 0;
for (int r=1; r<=n; r++) {
multiset<int> s;
s.insert(a[r]);
for (int l=r-1; l>=1; l--) {
s.insert(a[l]);
auto it = s.begin(); it++;
int MinSecond = *it;
auto it2 = s.rbegin(); it2++;
int MaxSecond = *it2;
if (MaxSecond - MinSecond <= k) {
res = max (res,r-l+1);
}
}
}
cout << res << '\n';
exit(0);
}
}
void solve () {
cin >> n >> k;
for (int i=1; i<=n; i++) {
cin >> a[i];
}
int l = 2, r = n, res = -1;
while (r >= l) {
int mid = (r+l) >> 1;
if (check(mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
cout << res << endl;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
```
</details>
## ALLMST - Editorial
Đầu tiên, ta sẽ gộp các nhóm cạnh có chung trọng số vào, nhóm cạnh có trọng số là $W$ gọi là nhóm $W$.
Dựa vào thuật toán Kruskal, ta nhận xét rằng, khi ta xét tới nhóm cạnh $W$ và đã DSU tất cả các cạnh trong các nhóm có trọng số $\le W-1$, ***cấu hình*** của DSU sẽ chỉ có $1$, nói cách khác, bất kể với từng nhóm cạnh $\le W-1$ ta đưa vào DSU các cạnh trong đó theo bất kì thứ tự nào, thì tính liên thông của đồ thị trong DSU sau khi xét toàn bộ các nhóm cạnh $\le W-1$ vẫn giữ nguyên.
Ta biết thêm được rằng, một cạnh $(u,v,c)$ chỉ được chọn để nằm trong một MST khi và chỉ khi trước đó $u$ và $v$ chưa liên thông. Từ đây, khi xét tới các cạnh trong nhóm $W$, giả sử đỉnh $u$ và đỉnh $v$ đã chung một vùng liên thông, chắc chắn nó sẽ không thể thuộc một MST nào cả, vậy nên ta bỏ qua. Ngược lại, với các cạnh có $u,v$ khác vùng liên thông, đây chắc chắn sẽ là các cạnh ***nằm trong ít nhất*** một MST.
Để kiểm tra xem các cạnh $(u,v)$ đó có nằm trong ***mọi MST*** hay không, ta cần xây dựng một đồ thị con chỉ gồm các cạnh này (các cạnh trong nhóm $W$ có $u,v$ khác vùng liên thông). Tuy nhiên, trong đồ thị con, ta sẽ không coi nó là cạnh $(u,v)$ nữa, mà là cạnh $(a,b)$, với $a$ là gốc của vùng liên thông chứa $u$, tương tự $b$ là gốc của vùng liên thông chứa $v$. Tưởng tượng như ta đang nối hai vùng liên thông này bằng cạnh $(a,b,i)$, với $i$ ở đây là index cạnh ban đầu, lưu ý cần lưu thêm index của cạnh vì sẽ có rất nhiều cạnh lặp, bởi dù hai cạnh $(u,v)$ và $(x,y)$ ban đầu khác nhau nhưng trong đồ thị mới nó có thể có cùng gốc nên quy về thành cạnh $(a,b)$.
Đến đây, ta sẽ có một đồ thị mới với các đỉnh là các vùng liên thông trong DSU (chú ý rằng đồ thị mới không nhất thiết liên thông với nhau), một cạnh sẽ nằm trong mọi MST khi và chỉ khi bỏ cạnh đó ra, đồ thị mới của ta bị tăng số vùng liên thông lên, bởi nếu không tăng thì tức là không cần dùng cạnh đó thì ta vẫn có thể giữ tính chất liên thông của đồ thị. Hay nói cách khác, các cạnh thỏa mãn chính là ***các cạnh cầu***.
Độ phức tạp: $O(n+m)$.
<details>
<summary>Nhấn để xem code</summary>
```cpp
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 500500;
struct edge {
int u,v,w,id;
bool operator < (const edge &o) const {
return w < o.w;
}
}e[N];
int tron() {
string s; cin >> s;
int res = 0;
for (auto c : s) {
res = res*10 + c - '0';
}
return res;
}
int n,m;
int f[N];
int find (int u) {
if (u == f[u]) return u;
return f[u] = find (f[u]);
}
bool join (int u, int v) {
u = find (u); v = find (v);
if (u == v) return false;
f[v] = u;
return true;
}
int res[N];
int low[N],num[N],cnt;
vector<pair<int,int> > a[N];
void dfs (int u, int p) {
low[u] = num[u] = ++cnt;
// cout << "veri tron " << u << ' ' << p << "?\n";
for (auto x : a[u]) {
int v = x.first, id = x.second;
if (id == p) continue;
if (num[v]) {
low[u] = min (low[u],num[v]);
}
else {
dfs (v,id);
low[u] = min (low[u],low[v]);
if (low[v] >= num[v]) {
res[e[id].id] = true;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i=1; i<=n; i++) f[i] = i;
for (int i=1; i<=m; i++) {
res[i] = 0;
e[i].u = tron(); e[i].v = tron(); e[i].w = tron();
e[i].id = i;
}
sort (e+1,e+m+1);
for (int i=1; i<=m; i++) {
int j = i;
vector<int> v;
while (j<=m&&e[j].w == e[i].w) {
v.push_back(j);
int u = e[j].u, v = e[j].v;
u = find (u); v = find (v);
if (u != v) {
low[u] = low[v] = num[u] = num[v] = 0;
a[u].clear(); a[v].clear();
}
j++;
}
for (auto id : v) {
int u = find(e[id].u); int v = find(e[id].v) ;
if (u != v) {
a[u].push_back({v,id});
a[v].push_back({u,id});
}
}
for (auto id : v) {
int u = find(e[id].u); int v = find(e[id].v) ;
if (u != v) {
if (!num[u]) dfs (u,0);
}
}
for (auto id : v) {
join(e[id].u,e[id].v);
}
i = j-1;
}
for (int i=1; i<=m; i++) {
if (res[i]) cout << "Yes ";
else cout << "No ";
}
}
```
</details>
## Dãy tăng kép - Editorial
Đầu tiên, để làm được bài này ta có nhận xét :
- Nếu ta có một dãy là một dãy tăng kép thì luôn có một cách chia như sau :
- Giả sử ta đang chia $i-1$ phần tử đầu tiên ra thành $2$ dãy con tăng, đến phần tử thứ $i$ thì
- Nếu phần tử thứ $i$ chỉ lớn hơn phần tử cuối cùng của dãy thứ nhất mà bé hơn hoặc bằng phần tử cuối cũng của dãy thứ hai thì ta chia số thứ $i$ vào dãy thứ nhất
- Nếu phần tử thứ $i$ chỉ lớn hơn phần tử cuối cùng của dãy thứ hai mà bé hơn hoặc bằng phần tử cuối cùng của dãy thứ nhất thì ta chia số thứ $i$ vào dãy thứ hai
+ Nếu phần tử thứ $i$ lớn hơn cả hai phần tử cuối cùng của hai dãy thì :
* Nếu phần tử cuối cùng dãy thứ nhất lớn hơn hoặc bằng dãy thứ hai thì ta chia số $i$ vào dãy thứ nhất
* Nếu phần tử cuối cùng dãy thứ hai lớn hơn dãy thứ nhất thì ta chia số $i$ vào dãy thứ hai
Từ nhận xét đó, ta có giải thuật $O(n^3)$ như sau :
- $dp[i][j]$ là số dãy con tính kép tính đến phần tử thứ $i$, và cách chia như trên cho ra hai dãy có phần tử cuối cùng là $a[i]$ và $j$
- Ta xét đến phần tử tiếp theo đưa vào dãy con kép là phần tử $a[k]$ $(k>i)$
+ Nếu $j≥a[k]>a[i]$: ta đưa $a[k]$ vào ngay sau $a[i]$ $(dp[k][j] += dp[i][j])$
+ Nếu $a[i]≥a[k]>j$: ta đưa $a[k]$ vào ngay sau $j$ $(dp[k][a[i]] += dp[i][j])$
+ Nếu $a[k]>a[i]≥j$: ta đưa $a[k]$ vào ngay sau $a[i]$ $(dp[k][j] += dp[i][j])$
+ Nếu $a[k]>j>a[i]$: ta đưa $a[k]$ vào ngay sau $j$ $(dp[k][a[i]] += dp[i][j])$
Thuật toán này cho ra đpt $O(n^3)$ , tuy nhiên khi cài đặt ta có thể nhận thấy việc tính $dp[i][j]$ bất kì đều sử dụng prefix-sum của các giá trị dp trước đó
Từ đó ta có thể dùng cấu trúc BIT để tối ưu xuống $O(n^2 log_2 (n))$, đủ tốt để vượt qua bài này.
<details>
<summary>Nhấn để xem code</summary>
```cpp=
// Flower_On_Stone
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2005;
const int MOD = 1000000007;
inline void add(int &x, int y)
{
x += y;
if (x >= MOD)
{
x -= MOD;
}
}
struct FenwickTree
{
int treeSize;
vector<int> nodes;
void init(int treeSize)
{
this->treeSize = treeSize;
nodes.assign(treeSize + 1, 0);
}
void update(int id, int val)
{
for (; id <= treeSize; id += (id & -id))
{
add(nodes[id], val);
}
}
int get(int id)
{
int resuft = 0;
for (; id >= 1; id -= (id & -id))
{
add(resuft, nodes[id]);
}
return resuft;
}
} ft[MAX_N];
int n;
int arr[MAX_N];
int dp[MAX_N][MAX_N], prefix[MAX_N][MAX_N];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifdef Flower_On_Stone
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
for (int i = 0; i <= n; i++)
{
ft[i].init(n);
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
dp[i][0] = 1;
// dp[i][j] += dp[k][j]; (a[k] < a[i] && a[k] >= a[j])
for (int j = 0; j < arr[i]; j++)
{
add(dp[i][j], (ft[j].get(arr[i] - 1) + MOD - (j > 0 ? ft[j].get(j - 1) : 0)) % MOD);
}
// dp[i][j] += dp[k][j]; (a[k] < a[i] && a[j] >= a[i]);
for (int j = arr[i]; j <= n; j++)
{
add(dp[i][j], ft[j].get(arr[i] - 1));
}
// dp[i][j] += dp[j][t]; (a[t] < a[i]) && (a[t] > a[j]);
for (int j = i - 1; j >= 0; j--)
{
int x = arr[j];
if (arr[i] - 1 > x)
{
add(dp[i][x], (prefix[j][arr[i] - 1] + MOD - prefix[j][x]) % MOD);
}
}
// dp[i][j] += dp[j][t] (a[t] < a[i]) && (a[i] <= a[j]);
for (int j = i - 1; j >= 0; j--)
{
int x = arr[j];
if (x >= arr[i])
{
add(dp[i][x], prefix[j][arr[i] - 1]);
}
}
for (int j = 0; j <= n; j++)
{
if (j > 0)
{
add(prefix[i][j], prefix[i][j - 1]);
}
prefix[i][j] = (prefix[i][j] + dp[i][j]) % MOD;
ft[j].update(arr[i], dp[i][j]);
}
add(ans, prefix[i][n]);
}
cout << (ans + MOD - n) % MOD;
return 0;
}
```
</details>
Sign in with Wallet
Connect another wallet