Hướng dẫn giải của duong3982oj Contest 03 - Điểm đặc biệt
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Subtask 1: ~n \le 100~.
Trâu, với mỗi ~i~, ta duyệt ~j > i~, ta thử bỏ phần tử ~a_j~ đi, và xem độ dài dãy con tăng dài nhất có thay đổi không, nếu có ta tăng kết quả lên ~1~.
Độ phức tạp: ~O~ (~n^3 \times log~ ~(n))~.
Subtask 2: ~n \le 1000~.
Gọi ~lis_i~ là độ dài dãy con tăng dài nhất bắt đầu từ ~a_i~.
Đến đây, ta có hai cách:
- Cách 1: Ta sẽ mô hình các điểm (~a_i, lis_i~) trên mặt phẳng tọa độ. Dễ thấy các đường gấp khúc đồng quy tại điểm nào thì điểm đó là một điểm đặc biệt.
Có nhiều cách thực hiện điều này, một trong những cách đó là sử dụng thuật toán đường quét.
- Cách 2 (cũng là cách ta có thể cải tiến lên subtask cuối):
Ta gọi một danh sách ~nxt_i~ là danh sách các điểm là điểm đặc biệt gần nhất sau vị trí ~i~.
Nhận xét: Nếu ~j~ là điểm đặc biệt của ~i~, ~k~ là điểm đặc biệt của ~j~ thì ~k~ là điểm đặc biệt của ~i~.
Vì vậy, giả sử các điểm đặc biệt đối với ~i~ là ~j, k~, thì:
- ~j, k~ có cùng đáp án (hay cùng số điểm đặc biệt).
- ~i~ sẽ có số điểm đặc biệt là ~j + 1~ hay ~k + 1~.
Mô hình các điểm này dưới dạng cây, ta thấy: số điểm đặc biệt đối với ~i~, chính là số điểm đặc biệt tối đa của các tổ tiên của ~j~ trên cây, khi ta thực hiên dựng cây với các cạnh nối ~i~ và từng phần tử của ~nxt_i~.
(ta chỉ nối cạnh ~j~ và ~i~ khi ~a_j > a_i~).
Độ phức tạp: ~O~ (~n^2 \times log~ ~(n)~).
Subtask 3: Dãy đồng biến hoặc nghịch biến:
- Nếu dãy là dãy đồng biến, ta sẽ có dãy kết quả là ~1, 2, \cdot \cdot \cdot, n~.
- Nếu dãy là dãy nghịch biến, ta sẽ có dãy kết quả là ~n~ số ~1~.
Độ phức tạp: ~O~ (~n~).
Subtask 4: ~n \le 10^6~
Nhận xét: Ta chỉ quan tâm tới ~j~ nhỏ nhất và ~j~ lớn nhất, trong tập các điểm ~j~ thuộc ~nxt_i~ và ~a_j > a_i~.
Độ phức tạp: ~O~ (~n \times log (n)~).
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int dp[1000005];
int nxt[1000005];
set<int> cnt[1000005];
struct Node{
int sum = 0, idmax = 0, idmin = 1e9;
};
vector<Node> t;
void update(int v, int tl, int tr, int pos, int val, int id){
if(tl == tr){
t[v].sum = val;
t[v].idmax = id;
t[v].idmin = id;
}
else{
int tm = (tl+tr)/2;
if(pos <= tm) update(v*2,tl,tm,pos,val,id);
else update(v*2+1,tm+1,tr,pos,val,id);
if(t[v*2].sum > t[v*2+1].sum){
t[v].sum = t[v*2].sum;
t[v].idmax = t[v*2].idmax;
t[v].idmin = t[v*2].idmin;
}else if(t[v*2].sum < t[v*2+1].sum){
t[v].sum = t[v*2+1].sum;
t[v].idmax = t[v*2+1].idmax;
t[v].idmin = t[v*2+1].idmin;
}else{
t[v].sum = t[v*2].sum;
t[v].idmax = max(t[v*2].idmax,t[v*2+1].idmax);
t[v].idmin = min(t[v*2].idmin, t[v*2+1].idmin);
}
}
}
Node query(int v, int tl, int tr, int l, int r){
if(l > tr || r < tl){
Node null;
return null;
}
if(l <= tl && tr <= r) return t[v];
int tm = (tl+tr)/2;
Node left = query(v*2,tl,tm,l,r);
Node right = query(v*2+1,tm+1,tr,l,r);
Node res;
if(left.sum > right.sum){
res.sum = left.sum;
res.idmax = left.idmax;
res.idmin = left.idmin;
}else if(left.sum < right.sum){
res.sum = right.sum;
res.idmax = right.idmax;
res.idmin = right.idmin;
}else{
res.sum = left.sum;
res.idmax = max(left.idmax,right.idmax);
res.idmin = min(left.idmin,right.idmin);
}
return res;
}
const int l = 20;
int d[1000005];
int up[1000005][25];
int lca(int u, int v){
if(d[u] < d[v]) swap(u,v);
for(int i = l; i >= 0; i--){
if(d[v] + (1<<i) <= d[u]) u = up[u][i];
}
if(u == v) return u;
for(int i = l; i >= 0; i--){
if(up[u][i] != up[v][i]){
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
int par[1000005], sz[1000005];
int find_set(int v){
if(par[v] == v) return v;
return find_set(par[v]);
}
void union_set(int u, int v){
u = find_set(u);
v = find_set(v);
if(u != v){
if(sz[u] < sz[v]) swap(u,v);
par[v] = u;
sz[u] += sz[v];
}
}
int spt[1000005][25];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
t.resize(4*n+5);
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++){
par[i] = i;
sz[i] = 1;
}
for(int i = n; i >= 1; i--){
Node res = query(1,1,n,a[i]+1,n);
dp[i] = res.sum+1;
update(1,1,n,a[i],dp[i],i);
int p = 0;
if(res.idmax){
if(res.idmax != res.idmin){
if(find_set(res.idmax) != find_set(res.idmin)) p = 0;
else p = lca(res.idmax, res.idmin);
}else p = res.idmax;
}
if(p){
union_set(i,p);
nxt[i] = p;
up[i][0] = p;
d[i] = d[p]+1;
for(int j = 1; j <= l; j++) up[i][j] = up[up[i][j-1]][j-1];
}
}
for(int i = 1; i <= n; i++) cout << d[i] << ' ';
return 0;
}
Bình luận