Hướng dẫn giải của duong3982oj Contest 03 - Cặp số chia hế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ả: , huyjavalt
Subtask 1
Với cây là đường thẳng, chúng ta có thể duyệt mọi cặp ~i~, ~j~ và tính toán.
Độ phức tạp: ~O~ (~n^2 \times q~).
Subtask 2
Cải tiến từ subtask 1, chúng ta có thể ~DFS~ hoặc ~BFS~ để tìm ra đường đi, sau đó vẫn duyệt ~i~ và ~j~ như subtask 1.
Độ phức tạp: ~O~ (~n^2 \times q~).
Subtask 3
Với ~a_i = a_j~, dễ thấy đáp án là ~x^2~ với ~x~ là số đỉnh trên đường đi đơn từ ~i~ đến ~j~.
Để tìm được ~x~, ta sẽ coi ~1~ là gốc của cây, và ~d_i~ là khoảng cách từ ~1~ đến đỉnh ~i~.
Ta sẽ dễ dàng tìm được ~x~ bằng cách tìm tổ tiên chung gần nhất.
Độ phức tạp: ~O~ (~n \times log (n)~).
Subtask 5
Ý tưởng đơn giản từ thuật toán MO. Để giải quyết các truy vấn ta có mảng ~choose_i~ là số con trong đoạn hiện tại chia hết cho i và ~cnt_i~ là số con có giá trị ~i~ trong đoạn hiện tại.
Khi ta thêm 1 giá trị ~x~ vào thì đáp án sẽ tăng lên bằng ~choose_x~ + ~\sum cnt_y~ (với y là ước của x khác x) + ~cnt_x * 2 - 1~ và tương tự với việc bỏ giá trị.
Subtask 6
Thay vì sử dụng Mo Algorithm trên đoạn thẳng, ta sẽ sử dụng Mo Algorithm trên cây.
Template MO trên cây được lấy từ blog https://codeforces.com/blog/entry/43230
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[40005];
vector<int> adj[40005];
pair<int,int> qr[40005];
vector<int> divi[40005];
const int l = 16;
int timer = 1;
int in[40005], out[40005], id[80005];
int up[40005][20];
void dfs(int v, int p){
id[timer] = v;
in[v] = timer++;
up[v][0] = p;
for(int i = 1; i <= l; i++) up[v][i] = up[up[v][i-1]][i-1];
for(auto u : adj[v]) if(u != p) dfs(u,v);
id[timer] = v;
out[v] = timer++;
}
bool is_anc(int u, int v){
return in[u] <= in[v] && out[v] <= out[u];
}
int lca(int u, int v){
if(is_anc(u,v)) return u;
if(is_anc(v,u)) return v;
for(int i = l; i >= 0; i--){
if(!is_anc(up[u][i],v)){
u = up[u][i];
}
}
return up[u][0];
}
int choose[40005];
int ans[40005];
int cnt[40005];
int n,q;
int block;
struct Qury{
int l,r,id,lc;
bool operator<(const Qury& other) const{
if(l/block != other.l/block) return l/block < other.l/block;
return r < other.r;
}
};
Qury query[40005];
int vis[40005];
int check[40005];
void add(int i, int& res){
res += choose[a[i]];
for(auto j : divi[a[i]]){
//cout << j << ' ' << a[i] << '\n';
if(j != a[i]){
choose[j]++;
res += cnt[j];
}
}
cnt[a[i]]++;
res += cnt[a[i]]*2-1;
//cout << "ADD" << ' ' << i << ' ' << res << endl;
}
void del(int i, int& res){
res -= choose[a[i]];
for(auto j : divi[a[i]]){
if(cnt[j] && j != a[i]) res -= cnt[j];
if(j != a[i]) choose[j]--;
}
res -= cnt[a[i]]*2-1;
cnt[a[i]]--;
//cout << "REV" << ' ' << i << ' ' << res << endl;
}
void cal(int i, int& res){
//cout << i << endl;
if(vis[i]) del(i,res);
else add(i,res);
vis[i] ^= 1;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> a[i];
check[a[i]] = 1;
}
for(int i = 1; i <= 4e4; i++) if(check[i]){
for(int j = i; j <= 4e4; j += i) if(check[j]){
divi[j].push_back(i);
}
}
for(int i = 2; i <= n; i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,1);
block = sqrtl(n);
for(int i = 1; i <= q; i++){
int u,v;
cin >> u >> v;
if(in[u] > in[v]) swap(u,v);
int r = lca(u,v);
if(r == u) query[i] = {in[u],in[v],i,r};
else query[i] = {out[u],in[v],i,r};
}
sort(query+1, query+q+1);
int curl = query[1].l, curr = query[1].l-1;
int res = 0;
for(int k = 1; k <= q; k++){
int l = query[k].l, r = query[k].r;
//cout << l << ' ' << r << ' ' << id[l] << ' ' << id[r] << ' ' << query[k].lc << endl;
while(curl < l){
cal(id[curl],res);
curl++;
}
while(curl > l){
curl--;
cal(id[curl],res);
}
while(curr < r){
curr++;
cal(id[curr],res);
}
while(curr > r){
cal(id[curr],res);
curr--;
}
if(query[k].lc != id[l] && query[k].lc != id[r]) cal(query[k].lc,res);
ans[query[k].id] = res;
if(query[k].lc != id[l] && query[k].lc != id[r]) cal(query[k].lc,res);
}
for(int k = 1; k <= q; k++) cout << ans[k] << '\n';
return 0;
}
Bình luận