A. Tối ưu hóa đường đi trên lưới và cây Cartesian
Vì kích thước lưới quá lớn, ta chỉ tập trung vào các điểm biên dạng (0, y). Đường đi được chia nhỏ thành các đoạn dựa trên vị trí cắt qua cột này. Đặt w[y] là độ dài tiền tố liên thông cực đại ở hàng thứ y. Hai điểm (0, u) và (0, v) (với u < v) có thể kết nối trực tiếp khi và chỉ khi tồn tại hàng x ≤ min(w[u], w[v]) sao cho độ cao t[x] vượt ngưỡng max(h[u..v]).
Thuật toán xây dựng cây Cartesian dạng min trên mảng độ cao h. Các cạnh hợp lệ tương ứng với mối quan hệ cha-trong cây. Sử dụng kỹ thuật nhảy nhị phân (binary lifting) để truy vấn tổ tiên chung nông nhất có thể đạt được trong khoảng [l, r]. Quá trình di chuyển ưu tiên bậc cha có độ sâu lớn hơn, đồng thời theo dõi cận trái/phải để đảm bảo không vượt ra ngoài phạm vi truy vấn.
Độ phức tạp: O((M + Q) log M).
#include <bits/stdc++.h>
#include "obstacles.h"
using namespace std;
const int MAXC = 200005, LOGC = 20;
int N, M, colLimit[MAXC], rowHgt[MAXC], maxT[MAXC][LOGC];
int stk[MAXC], leftPar[MAXC], rightPar[MAXC];
int upNode[MAXC][LOGC], limL[MAXC][LOGC], limR[MAXC][LOGC];
bool canLeft[MAXC], canRight[MAXC];
inline int queryMax(int L, int R) {
int k = 31 - __builtin_clz(R - L + 1);
return max(maxT[L][k], maxT[R - (1 << k) + 1][k]);
}
inline bool validEdge(int u, int v) {
return colLimit[min(u, v)] > queryMax(u, v);
}
void initialize(vector<int> T, vector<int> H) {
N = T.size(), M = H.size();
for (int i = 1; i <= N; ++i) colLimit[i] = max(colLimit[i - 1], T[i - 1]);
for (int i = 1; i < N; ++i) T[i] = min(T[i], T[i - 1]);
for (int i = 1; i <= M; ++i) {
rowHgt[i] = H[i - 1];
maxT[i][0] = H[i - 1];
}
for (int k = 1; k < LOGC; ++k)
for (int i = 1; i + (1 << k) - 1 <= M; ++i)
maxT[i][k] = max(maxT[i][k - 1], maxT[i + (1 << (k - 1))][k - 1]);
vector<pair<int, int>> nodes;
for (int i = 1; i <= M; ++i) {
auto pos = lower_bound(T.begin(), T.end(), rowHgt[i], greater<>()) - T.begin();
if (pos < N) nodes.push_back({rowHgt[i], i});
}
sort(nodes.begin(), nodes.end());
int rank[MAXC] = {0};
for (int i = 0; i < (int)nodes.size(); ++i) rank[nodes[i].second] = i + 1;
int top = 0;
for (int i = 1; i <= M; ++i) {
if (rank[i] == 0) continue;
while (top > 0 && rank[stk[top]] > rank[i]) {
rightPar[stk[top--]] = i;
}
leftPar[i] = (top == 0) ? 0 : stk[top];
stk[++top] = i;
}
fill(rightPar, rightPar + M + 2, M + 1);
for (int i = 1; i <= M; ++i) {
if (rank[i] == 0) continue;
canLeft[i] = (leftPar[i] > 0 && validEdge(leftPar[i], i));
canRight[i] = (rightPar[i] <= M && validEdge(i, rightPar[i]));
}
for (auto [h, idx] : nodes) {
int u = idx;
if (!canLeft[u] && !canRight[u]) upNode[u][0] = 0;
else if (!canRight[u]) upNode[u][0] = leftPar[u];
else if (!canLeft[u]) upNode[u][0] = rightPar[u];
else {
bool preferLeft = rank[leftPar[u]] < rank[rightPar[u]];
upNode[u][0] = preferLeft ? leftPar[u] : rightPar[u];
}
limL[u][0] = limR[u][0] = upNode[u][0];
}
for (int k = 1; k < LOGC; ++k)
for (int i = 0; i <= M + 1; ++i) {
int p = upNode[i][k - 1];
upNode[i][k] = upNode[p][k - 1];
limL[i][k] = min(limL[i][k - 1], limL[p][k - 1]);
limR[i][k] = max(limR[i][k - 1], limR[p][k - 1]);
}
}
int findHighest(int L, int R, int cur) {
for (int k = LOGC - 1; k >= 0; --k)
if (L <= limL[cur][k] && limR[cur][k] <= R) cur = upNode[cur][k];
while (L <= limL[cur][0] || limR[cur][0] <= R) {
for (int k = LOGC - 1; k >= 0; --k)
if (limL[cur][k] >= L) cur = limL[cur][k];
for (int k = LOGC - 1; k >= 0; --k)
if (limR[cur][k] <= R) cur = limR[cur][k];
}
return cur;
}
bool can_reach(int l, int r, int u, int v) {
return findHighest(l + 1, r + 1, u + 1) == findHighest(l + 1, r + 1, v + 1);
}
B. Mở rộng khoảng với chi phí bước nhảy khác nhau
Mô hình hóa vấn đề như việc mở rộng biên phải r từ [a, a]. Mỗi bước chi phí 1 mở rộng theo i + v[i], chi phí 2 theo i + w[i]. Sử dụng kỹ thuật nhân đôi (doubling) để mô phỏng quá trình. Để xử lý trường hợp đường đi bị cắt gãy giữa hai khối 2^k, ta duy trì đồng thời bảng tối ưu cho độ dài chính xác và lệch 1 đơn vị.
Truy vấn cực trị khoảng được tối ưu bằng bảng Sparse Table. Khi xử lý truy vấn, kết hợp hai trạng thái độ dài để đảm bảo không bỏ sót cấu hình tối ưu tại ranh giới.
Độ phức tạp: O((N + Q) log N).
#include <bits/stdc++.h>
#include "highest.h"
using namespace std;
const int MAXN = 500005, LOGN = 20;
int SZ, idxA[MAXN], idxB[MAXN], stA[MAXN][LOGN], stB[MAXN][LOGN];
int dpA[MAXN][LOGN], dpB[MAXN][LOGN];
inline int idx(int x) { return 1 << x; }
int bestA(int l, int r) {
int k = 31 - __builtin_clz(r - l + 1);
return (idxA[stA[l][k]] > idxA[stA[r - idx(k) + 1][k]]) ? stA[l][k] : stA[r - idx(k) + 1][k];
}
int bestB(int l, int r) {
int k = 31 - __builtin_clz(r - l + 1);
return (idxB[stB[l][k]] > idxB[stB[r - idx(k) + 1][k]]) ? stB[l][k] : stB[r - idx(k) + 1][k];
}
int qryA(int l, int r, int k) { return max(dpA[bestA(l, r)][k], dpA[bestB(l, r)][k]); }
int qryB(int l, int r, int k) { return max({r, dpB[bestA(l, r)][k], dpB[bestB(l, r)][k]}); }
vector<int> solve(vector<int>& V, vector<int>& W, vector<pair<int, int>>& Q) {
SZ = V.size();
for (int i = 1; i <= SZ; ++i) {
idxA[i] = min(SZ, V[i - 1] + i);
idxB[i] = min(SZ, W[i - 1] + i);
stA[i][0] = stB[i][0] = i;
}
for (int k = 1; k < LOGN; ++k)
for (int i = 1; i + idx(k) - 1 <= SZ; ++i) {
stA[i][k] = bestA(stA[i][k - 1], stA[i + idx(k - 1)][k - 1]);
stB[i][k] = bestB(stB[i][k - 1], stB[i + idx(k - 1)][k - 1]);
}
for (int i = 1; i <= SZ; ++i) {
dpA[i][0] = idxA[i];
dpB[i][0] = i;
dpB[i][1] = idxA[i];
dpA[i][1] = max(qryA(i, idxA[i], 0), idxB[i]);
}
for (int k = 2; k < LOGN; ++k)
for (int i = 1; i <= SZ; ++i) {
dpA[i][k] = max(qryA(i, dpA[i][k - 1], k - 1), qryB(i, idxB[bestB(i, dpB[i][k - 1])], k - 1));
dpB[i][k] = max(qryA(i, dpB[i][k - 1], k - 1), qryB(i, dpA[i][k - 1], k - 1));
}
vector<int> res;
for (auto [L, R] : Q) {
int u = L + 1, v = R + 1, curA = idxA[u], curB = u, cost = 1;
if (v <= idxA[u]) { res.push_back(v > u); continue; }
for (int k = LOGN - 1; k >= 0; --k) {
int nextPos = max(qryA(u, curA, k), qryB(u, idxB[bestB(u, curB)], k));
if (nextPos < v) {
cost += idx(k);
curB = max(qryA(u, curB, k), qryB(u, curA, k));
curA = nextPos;
}
}
res.push_back(cost + 1);
}
return res;
}
C. Phân đoạn tối ưu với tính đơn điệu quyết định và cây bền vững
Phần thứ nhất áp dụng quy hoạch động kết hợp chia để trị dựa trên tính đơn điệu của điểm quyết định. Tổng k phần tử lớn nhất trong khoảng được tính bằng cây đoạn bền vững (Persistent Segment Tree). Phần thứ hai tận dụng bất đẳng thức tứ giác của hàm trọng số khoảng để loại bỏ các ứng viên dư thừa. Sử dụng thuật toán quét (sweep line) cùng cây BIT để kiểm tra điều kiện thứ hạng phần tử nhanh chóng.
Độ phức tạp: O(N log^2 N).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 250005, VAL = 1e9 + 1;
struct PersTree {
int lc[MAXN * 32], rc[MAXN * 32], cnt[MAXN * 32];
ll sum[MAXN * 32];
int sz = 0, root[MAXN];
void update(int & cur, int prev, int L, int R, int val) {
cur = ++sz; cnt[cur] = cnt[prev] + 1; sum[cur] = sum[prev] + val;
if (L == R) return;
int mid = (L + R) >> 1;
if (val <= mid) { update(lc[cur], lc[prev], L, mid, val); rc[cur] = rc[prev]; }
else { update(rc[cur], rc[prev], mid + 1, R, val); lc[cur] = lc[prev]; }
}
ll kthSum(int k, int L, int R, int left, int right) {
if (L == R) return 1ll * k * L;
int mid = (L + R) >> 1, rightCnt = cnt[rc[right]] - cnt[rc[left]];
if (k <= rightCnt) return kthSum(k, mid + 1, R, rc[left], rc[right]);
return kthSum(k - rightCnt, L, mid, lc[left], lc[right]) + sum[rc[right]] - sum[rc[left]];
}
int kthVal(int k, int L, int R, int left, int right) {
if (L == R) return L;
int mid = (L + R) >> 1, rightCnt = cnt[rc[right]] - cnt[rc[left]];
return (k <= rightCnt) ? kthVal(k, mid + 1, R, rc[left], rc[right]) : kthVal(k - rightCnt, L, mid, lc[left], lc[right]);
}
} tree;
int N, K, pref[MAXN], arr[MAXN], optL[MAXN];
ll dp[MAXN];
ll queryCost(int l, int r) { return tree.kthSum(K, 1, VAL, tree.root[l - 1], tree.root[r]) - pref[r] + pref[l - 1]; }
void divideConquer(int l, int r, int optLbound, int optRbound) {
if (l > r) return;
int mid = (l + r) >> 1, bestIdx = -1;
dp[mid] = -1e18;
for (int i = optLbound; i <= min(mid - K + 1, optRbound); ++i) {
ll val = queryCost(i, mid);
if (val > dp[mid]) { dp[mid] = val; bestIdx = i; }
}
divideConquer(l, mid - 1, optLbound, bestIdx);
divideConquer(mid + 1, r, bestIdx, optRbound);
}
struct BIT {
int tr[MAXN], mn = VAL;
void reset() { fill(tr, tr + N + 1, VAL); }
void modify(int x, int v) { for (; x; x -= x & -x) tr[x] = min(tr[x], v); }
int query(int x) { for (mn = VAL; x <= N; x += x & -x) mn = min(mn, tr[x]); return mn; }
} bit;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> K;
for (int i = 1; i <= N; ++i) cin >> pref[i], pref[i] += pref[i - 1];
for (int i = 1; i <= N; ++i) { cin >> arr[i]; tree.update(tree.root[i], tree.root[i - 1], 1, VAL, arr[i]); }
divideConquer(K, N, 1, N);
bit.reset();
ll maxVal = *max_element(dp + K, dp + N + 1);
string ans(N, '0');
int ptr = 1;
for (int i = 1; i <= N; ++i) {
if (dp[i] == maxVal) {
while (ptr < optL[i]) {
if (queryCost(ptr, i) == maxVal) bit.modify(i, tree.kthVal(K, 1, VAL, tree.root[ptr - 1], tree.root[i]));
if (bit.query(ptr) <= arr[ptr]) ans[ptr - 1] = '1';
ptr++;
}
bit.modify(i, tree.kthVal(K, 1, VAL, tree.root[ptr - 1], tree.root[i]));
}
}
while (ptr <= N) { if (bit.query(ptr) <= arr[ptr]) ans[ptr - 1] = '1'; ptr++; }
cout << maxVal << "\n" << ans << "\n";
}
D. Thứ tự DFS và tối ưu cấu trúc lá trên cây
Với một đường dây chuyền, việc xuất ra thứ tự DFS từ hai đầu mút là đủ. Mở rộng cho cây, ta xuất thứ tự DFS từ từng nút lá. Để tránh trùng lặp và đảm bảo tính xác định của đường đi trung gian, ta loại bỏ lớp lá ngoài cùng, áp dụng đệ quy cho phần lõi, sau đó xen kẽ thứ tự duyệt con lá chẵn/lẻ. Trường hợp đặc biệt đồ thị dạng sao được xử lý riêng.
Độ phức tạp: O(N).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
vector<int> adj[MAXN], leafAdj[MAXN];
bool isLeaf[MAXN], reverseMode = false;
void traverse(int u, int parent) {
for (int v : adj[u]) if (v != parent) traverse(v, u);
if (reverseMode) {
for (int x : leafAdj[u]) cout << x << " ";
} else {
for (int i = (int)leafAdj[u].size() - 1; i >= 0; --i) cout << leafAdj[u][i] << " ";
}
cout << u << " ";
}
void solve() {
int n, leafCount = 0; cin >> n;
for (int i = 1; i <= n; ++i) { adj[i].clear(); leafAdj[i].clear(); isLeaf[i] = false; }
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u);
}
for (int i = 1; i <= n; ++i) if (adj[i].size() == 1) isLeaf[i] = true;
for (int i = 1; i <= n; ++i) {
vector<int> keep;
for (int x : adj[i]) {
if (isLeaf[x] || isLeaf[i]) leafAdj[i].push_back(x);
else keep.push_back(x);
}
adj[i] = keep;
}
for (int i = 1; i <= n; ++i) if (adj[i].size() == 1) leafCount++;
if (leafCount == 0) {
int root = -1;
for (int i = 1; i <= n; ++i) if (!isLeaf[i]) { root = i; break; }
cout << "2\n";
reverseMode = false; traverse(root, 0); cout << "\n";
reverseMode = true; traverse(root, 0); cout << "\n";
return;
}
cout << leafCount << "\n"; reverseMode = false;
for (int i = 1; i <= n; ++i) {
if (adj[i].size() == 1) { reverseMode = !reverseMode; traverse(i, 0); cout << "\n"; }
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t; while (t--) solve();
}
E. Đếm hoán vị với ràng buộc LDS và nguyên lý phản xạ
Phân tích ràng buộc trên dãy giảm dài nhất (LDS). Nếu LDS ≥ 3 thì không có lời giải. Với LDS = 2, phần tử nhỏ nhất ở cuối phải thỏa mãn điều kiện chặn. Chia hoán vị tại điểm cực đại: các phần tử nhỏ hơn phải sắp xếp tăng dần, các phần tử lớn hơn tự do. Sử dụng công thức tổ hợp kết hợp nguyên lý phản xạ (reflection principle) để đếm số cách chèn hợp lệ. Tối ưu truy vấn bằng BIT và mảng tiền tố/hậu tố.
Độ phức tạp: O((N + Q) log N).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 300005, MOD = 1e9 + 7;
ll power(ll a, ll b = MOD - 2) { ll r = 1; for (; b; a = a * a % MOD, b >>= 1) if (b & 1) r = r * a % MOD; return r; }
ll fac[MAXN * 2], ifac[MAXN * 2];
ll comb(int n, int k) { return (k < 0 || k > n) ? (n == -1 && k == -1 ? 1 : 0) : fac[n] * ifac[k] % MOD * ifac[n - k] % MOD; }
struct BIT {
int tree[MAXN], res;
void reset() { memset(tree, 0, sizeof(tree)); }
void update(int x, int v) { for (; x <= N; x += x & -x) tree[x] = max(tree[x], v); }
int query(int x) { for (res = 0; x; x -= x & -x) res = max(res, tree[x]); return res; }
} bitL, bitR;
int N, Q, arr[MAXN], ldsStart[MAXN], ldsEnd[MAXN], depth[MAXN];
int minValL[MAXN], minValR[MAXN], ans[Q];
vector<int> groups[MAXN];
vector<array<int, 2>> queries[MAXN];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N;
for (int i = fac[0] = ifac[0] = 1; i <= 2 * N; ++i) ifac[i] = power(fac[i] = fac[i - 1] * i % MOD);
fill(minValL, minValL + N + 1, 1e9); fill(minValR, minValR + N + 1, 1e9);
for (int i = 1; i <= N; ++i) {
cin >> arr[i];
ldsStart[i] = bitL.query(N - arr[i] + 1);
bitL.update(N - arr[i] + 1, i);
groups[ldsStart[i]].push_back(i);
minValL[i] = min(minValL[i - 1], arr[i]);
}
bitL.reset(); fill(depth, depth + N + 1, 1e9);
for (int i = N; i >= 1; --i) {
ldsEnd[i] = N - bitL.query(arr[i]) + 1;
bitL.update(arr[i], N - i + 1);
depth[ldsStart[i]] = min(depth[ldsStart[i]], ldsEnd[i]);
depth[i] = min(depth[i], depth[i + 1]);
minValR[i] = min(minValR[i + 1], arr[i]);
}
cin >> Q;
for (int i = 1, L, R; i <= Q; ++i) { cin >> L >> R; if (R < depth[L]) queries[L].push_back({R, i}); }
bitL.reset();
for (int i = N; i >= 1; --i) {
bitR.update(i, arr[i]);
for (int idx : groups[i]) bitL.update(idx, arr[idx]);
for (auto [R, qIdx] : queries[i]) {
if (min(minValL[i - 1], minValR[R + 1]) < bitL.query(R)) continue;
int large = N - bitR.query(R);
int small = N - (R - i + 1) - large;
ans[qIdx] = (comb(2 * large + small - 1, large + small - 1) + MOD - comb(2 * large + small - 1, large + small + 1)) % MOD;
}
}
for (int i = 1; i <= Q; ++i) cout << ans[i] << "\n";
}
F. Xác suất dừng trên cây phân tách khối (Block-Cut Tree)
Chuyển đổi đồ thị thành cây phân tách khối, phân biệt nút đơn và nút vòng. Định nghĩa xác suất di chuyển từ dưới lên: xác suất thoát khỏi khối sang nút anh em hoặc nút đơn, xác suất đi vào nút vòng, và xác suất kết thúc tại nút. Sử dụng phép nhân đa thức đơn giản hóa để cập nhật xác suất qua các nút vòng. Phân phối xác suất khởi đầu từ trên xuống.
Độ phức tạp: O(N^2) do cấu trúc vòng, có thể tối ưu hơn với FFT nhưng không cần thiết ở ràng buộc hiện tại.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 20005, MOD = 1e9 + 7;
vector<int> adj[MAXN], bcTree[MAXN];
int N, M, bcCount, inDeg[MAXN], disc[MAXN], low[MAXN], timer, stk[MAXN], top;
bool onStack[MAXN];
void findBCC(int u) {
disc[u] = low[u] = ++timer; stk[++top] = u; onStack[u] = true;
for (int v : adj[u]) {
if (!disc[v]) {
findBCC(v); low[u] = min(low[u], low[v]);
if (low[v] >= disc[u]) {
bcCount++;
while (onStack[v]) { bcTree[bcCount].push_back(stk[top]); onStack[stk[top--]] = false; }
bcTree[bcCount].push_back(u);
}
} else low[u] = min(low[u], disc[v]);
}
}
ll inv[MAXN], stayProb[MAXN], fArr[MAXN], gArr[MAXN], hArr[MAXN], wArr[MAXN], endProb[MAXN];
void dfsUp(int u, int parent) {
wArr[0] = 1;
for (int child : bcTree[u]) if (child != parent) dfsUp(child, u);
int k = 0;
for (int node : bcTree[u]) if (bcTree[node].size() > 1) {
gArr[node] = 1;
for (int v : bcTree[node]) gArr[node] = gArr[node] * gArr[v] % MOD;
wArr[++k] = 0;
for (int i = k; i > 0; --i) wArr[i] = (wArr[i] + wArr[i - 1] * gArr[node]) % MOD;
}
int degree = inDeg[u] - (u != 1);
for (int i = 0, cur = inv[degree] * stayProb[u] % MOD; i <= k; ++i) {
gArr[u] = (gArr[u] + cur * wArr[i]) % MOD;
if (i < k) cur = cur * 2 % MOD * inv[degree - 2 * i - 2] % MOD * (i + 1) % MOD * stayProb[u] % MOD;
}
for (int node : bcTree[u]) if (bcTree[node].size() > 1) {
for (int i = 0, cur = inv[degree] * stayProb[u] % MOD, z = 1; i < k; ++i) {
hArr[node] = (hArr[node] + cur * z) % MOD;
cur = cur * 2 % MOD * inv[degree - 2 * i - 2] % MOD * (i + 1) % MOD * stayProb[u] % MOD;
z = (wArr[i + 1] + (MOD - gArr[node]) * z) % MOD;
}
} else hArr[node] = gArr[u];
endProb[u] = (bcTree[parent].size() > 1) ? (1 + MOD - gArr[u]) % MOD : 1;
for (int node : bcTree[u]) {
if (bcTree[node].size() > 1) endProb[u] = (endProb[u] + hArr[node] * 2 % MOD * (gArr[node] + MOD - 1)) % MOD;
else endProb[u] = (endProb[u] + MOD - hArr[node]) % MOD;
}
}
void dfsDown(int u) {
for (int node : bcTree[u]) {
if (bcTree[node].size() == 1) {
fArr[bcTree[node][0]] = fArr[u] * hArr[node] % MOD;
dfsDown(bcTree[node][0]); continue;
}
ll z = fArr[u] * hArr[node] % MOD;
for (int i = 0; i < (int)bcTree[node].size(); ++i) { fArr[bcTree[node][i]] = (fArr[bcTree[node][i]] + z) % MOD; z = z * gArr[bcTree[node][i]] % MOD; }
z = fArr[u] * hArr[node] % MOD;
for (int i = bcTree[node].size() - 1; i >= 0; --i) { fArr[bcTree[node][i]] = (fArr[bcTree[node][i]] + z) % MOD; z = z * gArr[bcTree[node][i]] % MOD; }
for (int v : bcTree[node]) dfsDown(v);
}
}
void run() {
cin >> N >> M; bcCount = N; timer = top = 0;
for (int i = 1; i <= N; ++i) { cin >> stayProb[i]; stayProb[i] = (1 + MOD - stayProb[i]) % MOD; }
for (int i = 1, u, v; i <= M; ++i) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); inDeg[u]++; inDeg[v]++; }
findBCC(1); dfsUp(1, 0); fArr[1] = 1; dfsDown(1);
for (int i = 1; i <= N; ++i) cout << endProb[i] * fArr[i] % MOD << " \n"[i == N];
for (int i = 1; i <= N; ++i) adj[i].clear(), inDeg[i] = 0, disc[i] = low[i] = onStack[i] = 0;
for (int i = 1; i <= bcCount; ++i) endProb[i] = wArr[i] = fArr[i] = gArr[i] = hArr[i] = 0, bcTree[i].clear();
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
inv[1] = 1;
for (int i = 2; i < MAXN; ++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
int t; cin >> t; while (t--) run();
}
G. Kiểm tra cầu bằng cây DFS và truy vấn tổ tiên
Xây dựng cây DFS để phân loại cạnh cây và cạnh ngược. Điều kiện một cạnh là cầu phụ thuộc vào việc tồn tại kết nối ra ngoài cây con. Sử dụng cây đoạn trên dãy thứ tự vào (DFS entry) để truy vấn độ sâu tổ tiên nhỏ nhất/lớn nhất của các cạnh ngược. Xử lý đặc biệt cạnh xuất phát từ gốc. Kiểm tra điều kiện liên thông ngoài phạm vi Tv \ Tu.
Độ phức tạp: O(M log N).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, INF = 1e9, SZ = 1 << 17;
vector<int> adj[MAXN], backEdge[MAXN], upEdge[MAXN];
int N, M, depth[MAXN], minDepth[MAXN], entry[MAXN], exit[MAXN], timer, singleChild[MAXN];
struct SegTree {
int tree[SZ * 2];
SegTree() { fill(tree, tree + SZ * 2, -INF); }
void update(int x, int v) { for (x += SZ; x; x >>= 1) tree[x] = max(tree[x], v); }
void change(int x, int v) { for (tree[x += SZ] = v; x > 1; x >>= 1) tree[x >> 1] = max(tree[x], tree[x ^ 1]); }
int query(int l, int r) {
int res = -INF;
for (l += SZ - 1, r += SZ + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
if (!(l & 1)) res = max(res, tree[l ^ 1]);
if (r & 1) res = max(res, tree[r ^ 1]);
}
return res;
}
} treeMin, treeMax, treeCheck;
void dfsBuild(int u, int parent) {
vector<int> keep; minDepth[u] = depth[u] = depth[parent] + 1; entry[u] = ++timer;
for (int v : adj[u]) if (v != parent) {
if (!depth[v]) {
dfsBuild(v, u); minDepth[u] = min(minDepth[u], minDepth[v]); keep.push_back(v);
if (minDepth[v] >= depth[u]) singleChild[u] = singleChild[u] ? -1 : v;
} else if (depth[v] < depth[u]) { upEdge[u].push_back(v); backEdge[v].push_back(u); minDepth[u] = min(minDepth[u], depth[v]); }
}
adj[u] = keep; exit[u] = timer;
sort(upEdge[u].begin(), upEdge[u].end(), [](int a, int b) { return depth[a] < depth[b]; });
if (!upEdge[u].empty()) treeMin.change(entry[u], -depth[upEdge[u][0]]), treeMax.change(entry[u], depth[upEdge[u].back()]);
}
int nodeAtDepth[MAXN]; bool blocked[MAXN];
void dfsCheck(int u) {
nodeAtDepth[depth[u]] = u;
for (int v : adj[u]) dfsCheck(v);
for (int v : backEdge[u]) { upEdge[v].pop_back(); treeMax.change(entry[v], upEdge[v].empty() ? -INF : depth[upEdge[v].back()]); }
if (u == 1) {
if (adj[1].size() == 1 && adj[adj[1][0]].size() == 1) M--;
if (adj[1].size() == 2 && (adj[adj[1][0]].empty() || adj[adj[1][1]].empty())) M--;
return;
}
for (int v : adj[u]) {
if (singleChild[u] && singleChild[u] != v) continue;
bool ok = false;
for (int w : adj[v]) if (minDepth[w] >= depth[u]) { ok = true; break; }
if (!ok) M--;
}
if (singleChild[u]) return;
for (int v : adj[u]) {
int h = treeMax.query(entry[v], exit[v]);
treeCheck.update(minDepth[v], h);
if (minDepth[v] == h) blocked[h] = true;
}
for (int v : upEdge[u]) {
int ancestor = nodeAtDepth[depth[v] + 1];
if ((singleChild[v] && singleChild[v] != ancestor) || blocked[depth[v]]) continue;
bool cond1 = (v == 1 || min(-treeMin.query(entry[ancestor], entry[u] - 1), -treeMin.query(exit[u] + 1, exit[ancestor])) < depth[v]);
bool cond2 = treeCheck.query(1, depth[v] - 1) > depth[v];
if (cond1 || cond2) M--;
}
for (int v : adj[u]) treeCheck.update(minDepth[v], -INF), blocked[minDepth[v]] = false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> M;
for (int i = 1, u, v; i <= M; ++i) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }
dfsBuild(1, 0); dfsCheck(1); cout << M << "\n";
}
H. Định hướng cạnh và hành trình trên đồ thị BFS
Xây dựng cây BFS. Để giảm thiểu số cạnh cùng tầng, áp dụng chiến lược hợp nhất tập hợp tương tự DSU: hướng cạnh từ tập nhỏ sang tập lớn. Giải quyết xung đột bậc ra bằng cách quy định mỗi nút chỉ đi theo cạnh có nhãn lớn nhất. Sắp xếp cạnh theo bộ ba (max(depth), min(u, v), max(u, v)) giảm dần để đảm bảo tính chất ưu tiên. Hành trình được mô phỏng bằng cách luôn chọn cạnh ra có chỉ số lớn nhất.
Độ phức tạp: O(M log M).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
vector<int> adj[MAXN];
int depthArr[MAXN], compId[MAXN];
vector<int> label(int n, vector<pair<int, int>> S, int startNode) {
int m = S.size();
for (auto [u, v] : S) adj[u].push_back(v), adj[v].push_back(u);
queue<int> q; q.push(startNode); fill(depthArr, depthArr + n + 1, 1e9); depthArr[startNode] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) if (depthArr[v] > depthArr[u] + 1) { depthArr[v] = depthArr[u] + 1; q.push(v); }
}
vector<array<int, 4>> edges(m);
vector<int> res(m, 0);
for (int i = 0; i < m; ++i) {
int u = S[i].first, v = S[i].second;
edges[i] = {max(depthArr[u], depthArr[v]), min(u, v), max(u, v), i};
}
sort(edges.begin(), edges.end(), greater<>());
iota(compId, compId + n + 1, 1);
for (auto [d, u, v, idx] : edges) {
if (!compId[u] || !compId[v]) { res[idx] = !compId[u]; continue; }
if (depthArr[v] < depthArr[u] || (depthArr[u] == depthArr[v] && compId[v] > compId[u])) {
compId[v] += compId[u]; compId[u] = 0; res[idx] = 1;
} else {
compId[u] += compId[v]; compId[v] = 0; res[idx] = 0;
}
}
return res;
}
int travel(int n, int u, vector<pair<int, int>> edges) {
int maxLabel = 0;
for (auto [x, dir] : edges) if ((u > x) ^ dir) maxLabel = max(maxLabel, x);
return maxLabel;
}
I. Loại bỏ đoạn liên tục và kiểm tra tính chẵn lẻ
Trích xuất độ dài các đoạn liên tục thành chuỗi nhị phân dựa trên ngưỡng ≥ 2. Việc xóa đoạn tương đương với gộp các đoạn lân cận. Sử dụng BIT để theo dõi tổng độ dài còn lại. Kiểm tra tính hợp lệ bằng cách so sánh khoảng cách từ các đoạn '1' đến biên. Xây dựng lời giải bằng cách di chuyển đồng thời từ hai hướng về trung tâm, đảm bảo cân bằng số phần tử loại bỏ.
Độ phức tạp: O(N log N).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int N, M, lenArr[MAXN], first1[MAXN], last1[MAXN];
struct BIT {
int tree[MAXN], sum;
void add(int x, int v) { for (; x <= N; x += x & -x) tree[x] += v; }
int query(int x) { for (sum = 0; x; x -= x & -x) sum += tree[x]; return sum; }
} bit;
vector<int> ops;
bool isValid(int l, int r) {
int mid = (l + r) / 2;
if (lenArr[mid]) return true;
return l < r && max(0, first1[mid] - l) + max(0, r - last1[mid]) >= (r - l) / 2;
}
void construct(int l, int r) {
int mid = (l + r) / 2;
if (lenArr[mid]) { for (int i = (r - l) / 2; i > 0; --i) ops.push_back(mid); return; }
int leftDist = last1[mid] - l, rightDist = r - last1[mid];
while (leftDist > rightDist) { ops.push_back(first1[mid]); leftDist -= 2; }
while (leftDist > 0) { ops.push_back(last1[mid]); leftDist--; }
}
int posArr[MAXN], depthArr[MAXN], leftIdx[MAXN], rightIdx[MAXN];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N;
for (int i = 1, cnt = 0; i <= N; ++i) {
char c; cin >> c; bit.add(i, 1);
if (i == 1 || c != (char)(lenArr[cnt] ? 'a' + 1 : 'a' + 2)) { cnt++; depthArr[cnt] = 1; lenArr[cnt] = 0; }
else depthArr[cnt]++;
}
int totalSeg = cnt;
last1[totalSeg + 1] = totalSeg + 1;
for (int i = 1; i <= totalSeg; ++i) first1[i] = lenArr[i] ? i : first1[i - 1];
for (int i = totalSeg; i >= 1; --i) last1[i] = lenArr[i] ? i : last1[i + 1];
if (totalSeg & 1) {
if (!isValid(1, totalSeg)) return cout << "-1\n", 0;
construct(1, totalSeg);
} else {
bool found = false;
for (int i = 1; i <= totalSeg; i += 2) if (isValid(1, i) && isValid(i + 1, totalSeg)) {
construct(1, i); construct(i + 1, totalSeg); found = true; break;
}
if (!found) return cout << "-1\n", 0;
}
rightIdx[0] = 1; leftIdx[totalSeg + 1] = totalSeg;
for (int i = 1, p = 1; i <= totalSeg; ++i) { posArr[i] = p; p += depthArr[i]; leftIdx[i] = i - 1; rightIdx[i] = i + 1; }
vector<array<int, 2>> finalOps;
for (int idx : ops) {
int L = leftIdx[idx], R = rightIdx[idx], p = posArr[idx];
bit.add(p, -depthArr[idx]);
if (depthArr[idx] & 1) { finalOps.push_back({bit.query(p) + 1, 3}); depthArr[idx] -= 3; }
while (depthArr[idx] > 0) { finalOps.push_back({bit.query(p) + 1, 2}); depthArr[idx] -= 2; }
depthArr[idx] = depthArr[L] + depthArr[R]; posArr[idx] = posArr[L];
leftIdx[idx] = leftIdx[L]; rightIdx[idx] = rightIdx[R]; rightIdx[leftIdx[idx]] = leftIdx[rightIdx[idx]] = idx;
}
for (int x = rightIdx[0]; x <= totalSeg; x = rightIdx[x]) {
if (depthArr[x] & 1) { finalOps.push_back({1, 3}); depthArr[x] -= 3; }
while (depthArr[x] > 0) { finalOps.push_back({1, 2}); depthArr[x] -= 2; }
}
cout << finalOps.size() << "\n";
for (auto [s, l] : finalOps) cout << s << " " << l << "\n";
}
J. Phân hoạch đồ thị bằng cây tái cấu trúc Kruskal và LCT
Chiến lược tham lam chia đồ thị thành các khoảng liên thông cực đại. Với mỗi đầu trái l, tìm đầu phải r lớn nhất sao cho đồ thị con hợp lệ. Sử dụng cây tái cấu trúc Kruskal để duy trì tính chất MST. Khi duyệt giảm dần l, sử dụng Link-Cut Tree để cập nhật động các cạnh trong chu trình mới phát sinh. Cây đoạn theo dõi số lượng cạnh hợp lệ để xác định ranh giới r.
Độ phức tạp: O(N log N).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
struct SegTree {
int lazy[1 << 18];
array<int, 2> val[1 << 18];
void pushUp(int p) { val[p] = max(val[p << 1], val[p << 1 | 1]); }
void pushTag(int p, int k) { val[p][0] += k; lazy[p] += k; }
void pushDown(int p) { if (lazy[p]) { pushTag(p << 1, lazy[p]); pushTag(p << 1 | 1, lazy[p]); lazy[p] = 0; } }
void build(int l, int r, int p) {
val[p] = {-2, r}; if (l == r) return;
int mid = (l + r) >> 1; build(l, mid, p << 1); build(mid + 1, r, p << 1 | 1);
}
void update(int ul, int ur, int k, int l, int r, int p) {
if (ul <= l && r <= ur) return pushTag(p, k);
int mid = (l + r) >> 1; pushDown(p);
if (ul <= mid) update(ul, ur, k, l, mid, p << 1);
if (mid < ur) update(ul, ur, k, mid + 1, r, p << 1 | 1);
pushUp(p);
}
} tree;
int ch[MAXN][2], par[MAXN], mxVal[MAXN];
bool rev[MAXN];
void pushUpLCT(int p) { mxVal[p] = max({mxVal[ch[p][0]], p, mxVal[ch[p][1]]}); }
void pushTagLCT(int p) { if (p) { rev[p] ^= 1; swap(ch[p][0], ch[p][1]); } }
void pushDownLCT(int p) { if (rev[p]) { pushTagLCT(ch[p][0]); pushTagLCT(ch[p][1]); rev[p] = 0; } }
bool isRight(int p) { return p == ch[par[p]][1]; }
bool isRoot(int p) { return p != ch[par[p]][0] && p != ch[par[p]][1]; }
void rotate(int p) {
int u = par[p], v = par[u], k = isRight(p);
if (!isRoot(u)) ch[v][isRight(u)] = p;
ch[u][k] = ch[p][k ^ 1]; par[ch[p][k ^ 1]] = u;
ch[p][k ^ 1] = u; par[u] = p; par[p] = v;
pushUpLCT(u); pushUpLCT(p);
}
void splay(int p) {
vector<int> stk; stk.push_back(p);
for (int cur = p; !isRoot(cur); cur = par[cur]) stk.push_back(par[cur]);
for (int i = (int)stk.size() - 1; i >= 0; --i) pushDownLCT(stk[i]);
while (!isRoot(p)) {
if (!isRoot(par[p])) rotate(isRight(p) == isRight(par[p]) ? par[p] : p);
rotate(p);
}
}
int expose(int p) {
int last = 0;
for (; p; last = p, p = par[p]) { splay(p); ch[p][1] = last; pushUpLCT(p); }
return last;
}
void makeRoot(int p) { expose(p); pushTagLCT(p); }
void linkNodes(int u, int v) { makeRoot(u); splay(u); par[u] = v; }
void cutNodes(int u, int v) { makeRoot(u); expose(v); splay(v); ch[v][0] = par[u] = 0; pushUpLCT(v); }
int findMax(int u) { expose(u); pushDownLCT(u); for (; ch[u][0]; u = ch[u][0], pushDownLCT(u)); return u; }
int sArr[MAXN], tArr[MAXN];
vector<int> adjList[MAXN];
vector<int> partition_players(int n, int m, vector<int> X, vector<int> Y) {
vector<array<int, 2>> edges;
for (int i = 0; i < m; ++i) edges.push_back({Y[i] + 1, X[i] + 1});
sort(edges.begin(), edges.end());
for (int i = 1; i <= m; ++i) sArr[i] = edges[i - 1][1], tArr[i] = edges[i - 1][0], adjList[sArr[i]].push_back(i);
iota(mxVal + 1, mxVal + n + m + 1, 1);
tree.build(1, n, 1);
for (int i = n; i >= 1; --i) {
tree.update(i, i, 2, 1, n, 1); tree.update(i, n, -1, 1, n, 1);
for (int e : adjList[i]) {
int u = tArr[e];
if (findMax(i) != findMax(u)) { linkNodes(i, e + n); linkNodes(u, e + n); tree.update(u, n, 1, 1, n, 1); continue; }
makeRoot(i);
int maxEdge = mxVal[expose(u)] - n;
if (e >= maxEdge) continue;
if (u < tArr[maxEdge]) tree.update(u, tArr[maxEdge] - 1, 1, 1, n, 1);
cutNodes(sArr[maxEdge], maxEdge + n); cutNodes(tArr[maxEdge], maxEdge + n);
linkNodes(i, e + n); linkNodes(u, e + n);
}
}
vector<int> res;
for (int x = 1; x <= n; x = tree.val[1][1] + 1) res.push_back(tree.val[1][1] - x + 1);
return res;
}
K. Tối ưu hóa đường kính cây bằng mã hóa khối
Vấn đề thu gọn lại thành việc duy trì tập ứng viên hai đầu mút đường kính. Chia dãy đầu vào thành các khối, trong mỗi khối tiến hành loại bỏ các điểm không thể là đầu mút mới dựa trên tính chất hình học của cây. Truyền chỉ số khối qua các bước để giảm không gian tìm kiếm theo cấp số nhân. Giai đoạn cuối cùng sử dụng bảng tra cứu tiền tính toán để xác định chính xác cặp đầu mút từ tập nhỏ còn lại.
Độ phức tạp: O(N log N) nhờ vào việc nén thông tin hiệu quả.
#include <bits/stdc++.h>
#include "migrations.h"
using namespace std;
using pii = pair<int, int>
const int MAXN = 10005, BLOCKS[7] = {0, 33, 9, 5, 3, 3, 0}, END_IDX[7] = {0, 9828, 9968, 9988, 9994, 9996, 9998};
const int mapA[5][5] = {{0,1,4,5,6},{1,0,7,8,6},{2,3,8,4,5},{6,7,2,3,8},{8,3,4,5,7}};
const int mapB[5][3] = {{2,0,3},{0,4,5},{2,5,3},{2,1,3},{0,5,1}};
inline bool match(int a, int b, int c, int d) { return min(a,b)==min(c,d) && max(a,b)==max(c,d); }
namespace sender {
int depth[MAXN], up[MAXN][20], disArr[MAXN], xCand, yCand, maxDis, hCode;
vector<int> poolX, poolY, cx[MAXN], cy[MAXN];
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (int k = 19; ~k; --k) if (depth[up[u][k]] >= depth[v]) u = up[u][k];
if (u == v) return u;
for (int k = 19; ~k; --k) if (up[u][k] != up[v][k]) u = up[u][k], v = up[v][k];
return up[u][0];
}
int dist(int u, int v) { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
void update(int z) {
int d1 = dist(xCand, z), d2 = dist(z, yCand); maxDis = max({maxDis, d1, d2});
if (maxDis == d1) yCand = z;
else if (maxDis == d2) xCand = z;
}
int process(int u, int parent) {
depth[u] = depth[parent] + 1; up[u][0] = parent;
for (int k = 1; k < 20; ++k) up[u][k] = up[up[u][k - 1]][k - 1];
for (int b : {1, 2, 3, 4, 5}) {
if (u == END_IDX[b + 1]) {
vector<int> nx, ny;
for (int i : poolX) if (cx[i] == cx[xCand]) nx.push_back(i);
for (int i : poolY) if (cy[i] == cy[yCand]) ny.push_back(i);
poolX = nx; poolY = ny;
}
if (u == END_IDX[b]) {
for (int i = END_IDX[b - 1] + 1; i <= END_IDX[b]; ++i) poolX.push_back(i), poolY.push_back(i), update(i);
for (int i = 0, j = 0, k = 0, sx = poolX.size(), sy = poolY.size(); i < BLOCKS[b]; ++i) {
for (int t = j + sx / BLOCKS[b] + (i < sx % BLOCKS[b]); j < t; ++j) cx[poolX[j]] = i;
for (int t = k + sy / BLOCKS[b] + (i < sy % BLOCKS[b]); k < t; ++k) cy[poolY[k]] = i;
}
hCode = (b > 1) ? cx[xCand] * BLOCKS[b] + cy[yCand] : (xCand < yCand ? (swap(xCand, yCand), cx[xCand] * (cx[xCand] + 1) / 2 + cy[yCand]) : cx[xCand] * (cx[xCand] + 1) / 2 + cy[yCand]);
}
if (u > END_IDX[b] && u < END_IDX[b + 1] && hCode && (hCode - 1) / 4 == u - END_IDX[b]) return (hCode - 1) % 4 + 1;
}
if (u == N - 2) {
poolX.push_back(u - 1); poolX.resize(4, u);
poolY.push_back(u - 1); poolY.resize(4, u);
update(u - 1); update(u); cx[8] = u;
for (int i : {0, 1, 2, 3}) cx[i] = poolX[i], cx[i + 4] = poolY[i];
for (int c : {0, 1, 2, 3, 4}) for (int i : {0, 1}) for (int j : {2, 3, 4}) if (i < 1 || j < 4) {
if (match(xCand, yCand, cx[mapA[c][i]], cx[mapA[c][j]])) return hCode = c;
}
}
if (u == N - 1) {
update(u); cy[5] = u;
for (int i : {0, 1, 2, 3, 4}) cy[i] = cx[mapA[hCode][i]];
for (int c : {0, 1, 2, 3, 4}) for (int i : {0, 1}) {
if (match(xCand, yCand, cy[mapB[c][i]], cy[mapB[c][i + 1]])) return hCode = c;
}
}
if (u == N) {
update(u); cx[3] = u;
for (int i : {0, 1, 2}) cx[i] = cy[mapB[hCode][i]];
for (int i = 0, k = 0; i < 4; ++i) for (int j = i + 1; j < 4; ++j) if (i != 0 || j != 2) {
if (match(xCand, yCand, cx[i], cx[j])) return k;
k++;
}
}
return 0;
}
}
namespace receiver {
vector<int> poolX, poolY;
int cx[MAXN], cy[MAXN];
pii decode(vector<int> signals) {
signals.insert(signals.begin(), 0);
for (int b : {1, 2, 3, 4, 5}) {
for (int i = END_IDX[b - 1] + 1; i <= END_IDX[b]; ++i) poolX.push_back(i), poolY.push_back(i);
for (int i = 0, j = 0, k = 0, sx = poolX.size(), sy = poolY.size(); i < BLOCKS[b]; ++i) {
for (int t = j + sx / BLOCKS[b] + (i < sx % BLOCKS[b]); j < t; ++j) cx[poolX[j]] = i;
for (int t = k + sy / BLOCKS[b] + (i < sy % BLOCKS[b]); k < t; ++k) cy[poolY[k]] = i;
}
int hCode = 0, hx = 0, hy = 0;
for (int i = END_IDX[b]; i < END_IDX[b + 1]; ++i) if (signals[i]) hCode = (i - END_IDX[b]) * 4 + signals[i];
if (b > 1) { hx = hCode / BLOCKS[b]; hy = hCode % BLOCKS[b]; }
else { for (int i = 0; i < BLOCKS[b]; ++i) for (int j = 0; j <= i; ++j) if (i * (i + 1) / 2 + j == hCode) { hx = i; hy = j; } }
vector<int> nx, ny;
for (int i : poolX) if (cx[i] == hx) nx.push_back(i);
for (int i : poolY) if (cy[i] == hy) ny.push_back(i);
poolX = nx; poolY = ny;
}
poolX.push_back(N - 3); poolX.resize(4, N - 2);
poolY.push_back(N - 3); poolY.resize(4, N - 2);
cx[8] = N - 2;
for (int i : {0, 1, 2, 3}) cx[i] = poolX[i], cx[i + 4] = poolY[i];
cy[5] = N - 1;
for (int i : {0, 1, 2, 3, 4}) cy[i] = cx[sender::mapA[signals[N - 2]][i]];
cx[3] = N;
for (int i : {0, 1, 2}) cx[i] = cy[sender::mapB[signals[N - 1]][i]];
for (int i = 0, k = 0; i < 4; ++i) for (int j = i + 1; j < 4; ++j) if (i != 0 || j != 2) {
if (k++ == signals[N]) return {cx[i] - 1, cx[j] - 1};
}
return {0, 0};
}
}
int send_message(int n, int x, int parent) { return sender::process(x + 1, parent + 1); }
pii longest_path(vector<int> S) { return receiver::decode(S); }
L. Nhân ma trận và quy hoạch động trên khoảng với cây đoạn
Chuyển bài toán thành bài toán nhân ma trận trên nửa vành (semiring) với phép toán min-plus. Nén tọa độ bằng phép modulo để nhóm các thông tin tương đồng. Duy trì tích ma trận trên các khoảng bằng cây đoạn. Tối ưu hóa các khối liên tiếp giống nhau bằng phép lũy thừa ma trận nhanh. Trích xuất kết quả tối ưu từ trạng thái cuối cùng.
Độ phức tạp: O((N + P) log M).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 40005, SZ = 1 << 16;
const ll INF = 4e18;
struct Matrix {
ll data[4][4];
Matrix() { for (int i = 0; i < 4; ++i) for (int j = 0; j < 4; ++j) data[i][j] = INF; }
friend Matrix operator * (const Matrix & A, const Matrix & B) {
Matrix C;
for (int i = 0; i < 4; ++i) for (int k = 0; k < 4; ++k) if (A.data[i][k] != INF)
for (int j = 0; j < 4; ++j) if (B.data[k][j] != INF)
C.data[i][j] = min(C.data[i][j], A.data[i][k] + B.data[k][j]);
return C;
}
};
Matrix buildGap(ll d) {
Matrix m; m.data[0][0] = m.data[3][3] = d; m.data[1][1] = m.data[2][2] = 2 * d;
m.data[0][2] = m.data[0][3] = m.data[1][2] = m.data[1][3] = 0; return m;
}
struct SegmentInfo {
ll l, r; Matrix mat;
SegmentInfo() { l = r = -1; }
friend SegmentInfo operator * (const SegmentInfo & A, const SegmentInfo & B) {
if (A.l < 0 || B.l < 0) return A.l >= 0 ? A : B;
SegmentInfo res; res.l = A.l; res.r = B.r;
res.mat = A.mat * buildGap(B.l - A.r) * B.mat;
return res;
}
friend SegmentInfo operator + (const SegmentInfo & A, ll d) {
SegmentInfo res = A; res.l += d; res.r += d; return res;
}
};
SegmentInfo treeArr[SZ * 2], items[MAXN];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
ll M; int N1, N2; cin >> M >> N1 >> N2;
for (int i = 1; i <= N1 + N2; ++i) {
ll L, R; cin >> L >> R; items[i].l = L; items[i].r = R;
if (i <= N1) items[i].mat.data[2][0] = items[i].mat.data[3][1] = 0;
else { for (int k = 0; k < 4; ++k) items[i].mat.data[k][k] = 0; }
}
sort(items + 1, items + N1 + N2 + 1, [](const auto & a, const auto & b) { return a.l % M < b.l % M; });
map<ll, vector<int>> events;
for (int i = 1; i <= N1 + N2; ++i) {
events[items[i].l / M].push_back(i);
events[items[i].r / M + 1].push_back(-i);
items[i].r = items[i].l %= M;
}
SegmentInfo total;
for (auto it = events.begin(); it != events.end(); ++it) {
auto nxt = next(it); if (nxt == events.end()) break;
ll L = it->first, R = nxt->first;
for (int idx : it->second) {
if (idx > 0) { treeArr[idx + SZ] = items[idx]; for (int p = (idx + SZ) >> 1; p; p >>= 1) treeArr[p] = treeArr[p << 1] * treeArr[p << 1 | 1]; }
else { treeArr[SZ - idx] = SegmentInfo(); for (int p = (SZ - idx) >> 1; p; p >>= 1) treeArr[p] = treeArr[p << 1] * treeArr[p << 1 | 1]; }
}
SegmentInfo cur = treeArr[1]; ll offset = L * M;
if (cur.l < 0) continue;
for (int k = 0; k <= 31 - __builtin_clz(R - L); ++k) {
if ((R - L) >> k & 1) { total = total * (cur + offset); offset += M << k; }
cur = cur * (cur + (M << k));
}
}
ll ans = INF;
for (int i : {2, 3}) for (int j : {0, 1}) ans = min(ans, total.mat.data[i][j]);
cout << ans << "\n";
}
M. Duy trì thứ tự trên miền giá trị với cây đoạn và BIT
Chuyển đổi bài toán sang làm việc trên miền giá trị thay vì chỉ số vị trí. Sử dụng hàng đợi ưu tiên ảo để quản lý các điểm chèn. Cây đoạn theo dõi các khoảng giá trị hợp lệ, BIT hỗ trợ truy vấn thứ tự nhanh. Các phép cập nhật được xử lý bằng cách di chuyển điều kiện chặn dọc theo cấu trúc cây, đảm bảo tính chất đơn điệu của các ngưỡng.
Độ phức tạp: O((N + Q) log N).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005, INF = 1e9;
struct LazyPQ {
priority_queue<int, vector<int>, greater<>> active, removed;
void push(int x) { active.push(x); }
void remove(int x) { removed.push(x); }
int top() { while (!removed.empty() && active.top() == removed.top()) active.pop(), removed.pop(); return active.top(); }
} pq[MAXN];
int N, Q, arr[MAXN], posArr[MAXN], valArr[MAXN], occ[MAXN], prefOcc[MAXN];
struct BIT {
int tree[MAXN];
void add(int x, int v) { for (; x <= N; x += x & -x) tree[x] += v; }
int sum(int x) { int s = 0; for (; x; x -= x & -x) s += tree[x]; return s; }
int findKth(int k) {
int x = 0;
for (int i = 1 << 19; i; i >>= 1) if (x + i <= N && k > tree[x + i]) k -= tree[x + i], x += i;
return x + 1;
}
} bit;
struct SegTree {
int tree[1 << 21 | 5][2], lazy[1 << 21 | 5];
void pushUp(int p) { tree[p][0] = max(tree[p << 1][0], tree[p << 1 | 1][0]); tree[p][1] = min(tree[p << 1][1], tree[p << 1 | 1][1]); }
void pushTag(int p, int k) { lazy[p] += k; tree[p][0] += k; tree[p][1] += k; }
void pushDown(int p) { if (lazy[p]) { pushTag(p << 1, lazy[p]); pushTag(p << 1 | 1, lazy[p]); lazy[p] = 0; } }
void build(int l = 1, int r = N, int p = 1) {
tree[p][0] = 0; tree[p][1] = INF;
if (l == r) return; int mid = (l + r) >> 1;
build(l, mid, p << 1); build(mid + 1, r, p << 1 | 1);
}
void update(int x, int type, int l = 1, int r = N, int p = 1) {
if (l == r) { tree[p][type] = tree[p][type ^ 1]; tree[p][type ^ 1] = type ? -INF : INF; return; }
int mid = (l + r) >> 1; pushDown(p);
(x <= mid ? update(x, type, l, mid, p << 1) : update(x, type, mid + 1, r, p << 1 | 1));
pushUp(p);
}
void addRange(int ul, int ur, int k, int l = 1, int r = N, int p = 1) {
if (ul > ur) return;
if (ul <= l && r <= ur) return pushTag(p, k);
int mid = (l + r) >> 1; pushDown(p);
if (ul <= mid) addRange(ul, ur, k, l, mid, p << 1);
if (mid < ur) addRange(ul, ur, k, mid + 1, r, p << 1 | 1);
pushUp(p);
}
int findFirst(int x, int type, int l = 1, int r = N, int p = 1) {
if (tree[p][type] != type) return 0;
if (l == r) return l;
int mid = (l + r) >> 1; pushDown(p);
return (x <= mid ? findFirst(x, type, l, mid, p << 1) : 0) ? : findFirst(x, type, mid + 1, r, p << 1 | 1);
}
} tree;
void insertVal(int x) {
int y = valArr[pq[x].top()], idx = bit.sum(x - 1) + 1;
tree.addRange(x, x, y - posArr[x]); posArr[x] = y;
if (bit.findKth(idx) != x || y >= idx) return;
int nextPos = (x < N ? tree.findFirst(x + 1, 0) : 0);
if (nextPos) tree.addRange(nextPos + 1, N, -1), tree.update(nextPos, 1), bit.add(nextPos, 1);
tree.addRange(x + 1, N, 1), tree.update(x, 0), bit.add(x, -1);
}
void removeVal(int x) {
int y = valArr[pq[x].top()], idx = bit.sum(x - 1) + 1;
tree.addRange(x, x, y - posArr[x]); posArr[x] = y;
if (bit.findKth(idx) == x || y < idx) return;
int nextPos = (x < N ? tree.findFirst(x + 1, 1) : 0);
if (nextPos) tree.addRange(nextPos + 1, N, 1), tree.update(nextPos, 0), bit.add(nextPos, -1);
tree.addRange(x + 1, N, -1), tree.update(x, 1), bit.add(x, 1);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> Q;
for (int i = 1; i <= N; ++i) pq[i].push(N + 1);
for (int i = 1; i <= N; ++i) { cin >> arr[i]; prefOcc[i] = prefOcc[i - 1] + (!arr[i]); if (arr[i] > 0) pq[arr[i]].push(i); }
valArr[N + 1] = prefOcc[N]; tree.build();
for (int i = 1, z = 0; i <= N; ++i) {
posArr[i] = valArr[pq[i].top()]; tree.addRange(i, i, posArr[i]);
if (posArr[i] > z) bit.add(i, 1), ++z, tree.update(i, 1), tree.addRange(i + 1, N, -1);
}
for (int x, k, y; Q--;) {
cin >> x >> k >> y;
if (arr[x] > 0) { pq[arr[x]].remove(x); removeVal(arr[x]); }
arr[x] = k;
if (arr[x] > 0) { pq[arr[x]].push(x); insertVal(arr[x]); }
cout << (arr[y] > 0 ? arr[y] : bit.findKth(prefOcc[y])) << "\n";
}
}
N. Mô phỏng tô màu và hợp thành hàm từng khúc
Trích xuất trạng thái dãy thành số lượng điểm đỏ ở tiền tố và điểm xanh ở hậu tố. Mỗi phép toán làm thay đổi trạng thái theo quy tắc tuyến tính từng đoạn. Sử dụng cây đoạn để lưu trữ và hợp thành các hàm affine trên các khoảng xác định. Tận dụng tính chất logarit của quá trình mở rộng biên để mô phỏng trực tiếp các bước thay đổi quan trọng. Tối ưu hóa bằng cách nhóm các trạng thái theo lũy thừa của 2.
Độ phức tạp: O((N + Q) log^2 N).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 120005;
int N, M, Q, posArr[MAXN];
struct SegTree {
vector<array<int, 2>> func[1 << 18 | 5];
auto locate(int p, int k) { return lower_bound(func[p].begin(), func[p].end(), array<int, 2>{k, -N}); }
void build(int l = 1, int r = M, int p = 1) {
if (l == r) {
if (posArr[l] == N) func[p] = {{N - 1, 0}, {N, -1}};
else if (2 * posArr[l] > N) func[p] = {{N - posArr[l] - 1, posArr[l] + 1}, {posArr[l] - 1, posArr[l] - N}, {N, posArr[l] - N - 1}};
else func[p] = {{posArr[l] - 1, posArr[l] + 1}, {N - posArr[l], posArr[l]}, {N, posArr[l] - N - 1}};
return;
}
int mid = (l + r) >> 1, leftChild = p << 1, rightChild = p << 1 | 1, L = 0;
build(l, mid, leftChild); build(mid + 1, r, rightChild);
for (auto [R, z] : func[leftChild]) {
auto s = locate(rightChild, L + z), t = locate(rightChild, R + z);
for (; s < t; ++s) func[p].push_back({(*s)[0] - z, z + (*s)[1]});
func[p].push_back({R, z + (*s)[1]}); L = R + 1;
}
}
void query(int ul, int ur, int & k, int l = 1, int r = M, int p = 1) {
if (ul <= l && r <= ur) return k += (*locate(p, k))[1], void();
int mid = (l + r) >> 1;
if (ul <= mid) query(ul, ur, k, l, mid, p << 1);
if (mid < ur) query(ul, ur, k, mid + 1, r, p << 1 | 1);
}
} tree;
int blueCnt[MAXN], redCnt[MAXN], bStart, rStart, lBound[MAXN], rBound[MAXN], nextJump[18][18][MAXN];
ll gl[18][MAXN], gr[18][MAXN];
char color[MAXN];
int applyTransform(int L, int R, int k) { tree.query(L, R, k); return k; }
int simulate(int x, int y) {
int l = 1, r = 1, logL, logR, z;
auto getLog = [&](int v) { return v ? 31 - __builtin_clz(v) + 1 : 0; };
auto checkColor = [&](int i) { return i <= lBound[l] ? 0 : (i > N - rBound[r] ? 1 : (color[i] == 'B' ? 1 : 0)); };
auto countBlue = [&]() { return rBound[r] + blueCnt[N - rBound[r]] - blueCnt[lBound[l]]; };
auto moveL = [&](int s, int t) { return min((ll)lBound[l], l + min(gl[logL][t] - gl[logL][s - 1], (ll)N)); };
auto moveR = [&](int s, int t) { return min((ll)rBound[r], r + min(gr[logR][t] - gr[logR][s - 1], (ll)N)); };
for (; x <= y; ++x) {
logL = getLog(lBound[l]); logR = getLog(rBound[r]); z = min(y + 1, nextJump[logL][logR][x]);
for (int step = 1 << 31 - __builtin_clz(z - x + 1); step; step >>= 1)
if (x + step <= z && lBound[moveL(x, x + step - 1)] + rBound[moveR(x, x + step - 1)] < N) {
lBound[l] = moveL(x, x + step - 1); rBound[r] = moveR(x, x + step - 1); x += step;
}
if (x > y) break;
int p = posArr[x] + checkColor(posArr[x]), c = countBlue();
if (c >= p) { if (p >= c - rBound[r]) return applyTransform(x + 1, y, N - c + p); lBound[++l] = p; }
else { c = N - c; p = N + 1 - p; if (p >= c - lBound[l]) return applyTransform(x + 1, y, c - p); rBound[++r] = p; }
}
return N - countBlue();
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> M;
for (int i = 1; i <= N; ++i) { cin >> color[i]; blueCnt[i] = blueCnt[i - 1] + (color[i] == 'B' ? 1 : 0); if (color[i] == 'B') lBound[++bStart] = i - 1; }
for (int i = 1; i <= M; ++i) cin >> posArr[i];
for (int i = N; i >= 1; --i) if (color[i] == 'R') rBound[++rStart] = N - i;
lBound[++bStart] = N; rBound[++rStart] = N;
for (int x = 0; x < 18; ++x) for (int y = 0; y < 18; ++y) {
int L = (x ? 1 << (x - 1) : 0), R = (y ? 1 << (y - 1) : 0);
for (int i = M + 1; i >= 1; --i) nextJump[x][y][i] = (i > M || (L < posArr[i] && posArr[i] <= N - R)) ? i : nextJump[x][y][i + 1];
}
for (int x = 0; x < 18; ++x) {
int d = (x ? 1 << (x - 1) : 0);
for (int i = 1; i <= M; ++i) {
gl[x][i] = gl[x][i - 1] + (posArr[i] <= d ? posArr[i] : 0);
gr[x][i] = gr[x][i - 1] + (posArr[i] > N - d ? N - posArr[i] : 0);
}
}
tree.build(); cin >> Q;
for (int L, R; Q--;) cin >> L >> R, cout << simulate(L, R) << "\n";
}
O. Che phủ khoảng và nhảy nhị phân trên lưới thu gọn
Thu gọn lưới thành các thành phần liên thông để xác định khoảng hàng mà mỗi thành phần chiếm giữ. Bài toán quy về việc tìm đường đi liên kết các khoảng chồng lấn với chi phí tối thiểu. Sử dụng kỹ thuật nhảy nhị phân để tăng tốc quá trình di chuyển giữa các khoảng liền kề. Xử lý riêng trường hợp chi phí cố định bằng cách duy trì trạng thái bước nhảy lệch đơn vị.
Độ phức tạp: O((N + Q) log N).
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int N, W, _, Q, parentArr[MAXN * 2], compId[MAXN * 2], L[MAXN * 2], R[MAXN * 2];
inline int idx(int r, int c) { return (r - 1) * W + c; }
int findSet(int x) { return parentArr[x] == x ? x : parentArr[x] = findSet(parentArr[x]); }
int hArr[MAXN], bArr[MAXN], maxR[MAXN], fArr[MAXN][20], gArr[MAXN][20], lInt[MAXN], rInt[MAXN];
int nextBound(int x) { return upper_bound(lInt + 1, lInt + Q + 1, x) - lInt; }
int jumpPos(int x) { return x ? min(hArr[x], rInt[nextBound(x)]) : rInt[1]; }
int solve() {
cin >> Q; vector<int> ids;
for (int i = 0, r, c; i < Q; ++i) { cin >> r >> c; ids.push_back(compId[idx(r, c)]); }
sort(ids.begin(), ids.end()); ids.erase(unique(ids.begin(), ids.end()), ids.end());
if (ids.size() == 1) return 0;
sort(ids.begin(), ids.end(), [&](int a, int b) { return R[a] != R[b] ? R[a] < R[b] : L[a] > L[b]; });
int qCnt = 0;
for (int id : ids) if (L[id] > lInt[qCnt]) lInt[++qCnt] = L[id], rInt[qCnt] = R[id];
lInt[qCnt + 1] = rInt[qCnt + 1] = N + 1;
if (maxR[lInt[1]] < rInt[qCnt]) return -1;
int u = bArr[rInt[1]], v = 0, w, steps = 1;
while (v <= rInt[1] && u < lInt[qCnt]) w = max(jumpPos(v), bArr[jumpPos(u)]), v = u, u = w, steps++;
while (u < lInt[qCnt]) {
int t = nextBound(v);
for (int k = 19; ~k; --k) {
w = max(fArr[u][k], gArr[hArr[v]][k]);
if (w < lInt[t]) v = max(fArr[v][k], gArr[u][k]), u = w, steps += (1 << k);
}
while (v <= rInt[t] && u < lInt[qCnt]) w = max(jumpPos(v), bArr[jumpPos(u)]), v = u, u = w, steps++;
}
return steps;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> W >> _;
iota(parentArr + 1, parentArr + N * W + 1, 1);
for (int i = 1; i <= N; ++i) for (int j = 1; j < W; ++j) { char c; cin >> c; if (c == '1') parentArr[findSet(idx(i, j))] = findSet(idx(i, j + 1)); }
for (int i = 1; i < N; ++i) for (int j = 1; j <= W; ++j) { char c; cin >> c; if (c == '1') parentArr[findSet(idx(i, j))] = findSet(idx(i + 1, j)); }
for (int i = 1; i <= N; ++i) for (int j = 1; j <= W; ++j) if (parentArr[idx(i, j)] == idx(i, j)) compId[idx(i, j)] = ++Q;
for (int i = 1; i <= N; ++i) for (int j = 1; j <= W; ++j) {
int c = compId[idx(i, j)] = compId[findSet(idx(i, j))]; L[c] = min(L[c], i); R[c] = max(R[c], i);
}
for (int i = 1; i <= Q; ++i) hArr[L[i]] = max(hArr[L[i]], R[i]);
for (int i = 1; i <= N; ++i) hArr[i] = max({hArr[i], hArr[i - 1], i});
for (int i = N; i >= 1; --i) maxR[i] = max(maxR[hArr[i]], i);
for (int i = 1, z; i <= N; ++i) { cin >> z; bArr[i] = (z > 1 ? bArr[i - 1] : i); }
for (int i = 1; i <= N; ++i) fArr[i][0] = max(i, bArr[hArr[i]]), gArr[i][0] = i;
for (int k = 1; k < 20; ++k) for (int i = 1; i <= N; ++i) {
fArr[i][k] = max(fArr[fArr[i][k - 1]][k - 1], gArr[hArr[gArr[i][k - 1]]][k - 1]);
gArr[i][k] = max(fArr[gArr[i][k - 1]][k - 1], gArr[fArr[i][k - 1]][k - 1]);
}
while (_--) cout << solve() << "\n";
}
P. Tìm kiếm nhị phân phân số và cắt tỉa tìm kiếm
Tìm kiếm nhị phân trên tập các phân số tối giản. Với mỗi ngưỡng, kiểm tra tính khả thi bằng cách mô phỏng lịch trình tham lam. Để giảm độ phức tạp mũ, chỉ phân nhánh tìm kiếm vào hai thời điểm sớm nhất và sớm thứ hai có thể xảy ra. Chứng minh rằng các lựa chọn khác sẽ dẫn đến trạng thái không tối ưu hoặc trùng lặp. Sử dụng mảng tiền tố và bảng tra cứu để tính toán nhanh điều kiện ràng buộc.
Độ phức tạp: O((2^N + L) * N * log L) với cắt tỉa mạnh.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, INF = 1e9;
string grid[18];
int N, M, colCnt[MAXN], fTable[19][MAXN], dTable[18][MAXN], gTable[18][MAXN], X, Y, sleepTime[18];
bool searchSchedule(int k, int mask) {
if (mask == (1 << N) - 1) return true;
array<int, 2> best = {INF, -1}, secondBest = {INF, -1};
for (int i = 0; i < N; ++i) if (!(mask >> i & 1)) {
int h = k ? sleepTime[k - 1] : 0;
for (int j = 0; j < k; ++j) {
int r = sleepTime[j] + X;
if (h < r) h = max(h, min(r, fTable[k - j + 1][(r - 1) / Y] * Y));
}
if (dTable[i][h / Y] * Y - h % Y < X) {
if (h / Y == M || gTable[i][h / Y + 1] < 0) continue;
h = gTable[i][h / Y + 1] * Y;
}
if (h < best[0]) { secondBest = best; best = {h, i}; }
else if (h < secondBest[0]) secondBest = {h, i};
}
if (best[1] != -1) { sleepTime[k] = best[0]; if (searchSchedule(k + 1, mask | (1 << best[1]))) return true; }
if (secondBest[1] != -1) { sleepTime[k] = secondBest[0]; if (searchSchedule(k + 1, mask | (1 << secondBest[1]))) return true; }
return false;
}
bool checkThreshold() {
for (int i = 0; i < N; ++i) {
dTable[i][M] = 0; gTable[i][M] = -1;
for (int j = M - 1; j >= 0; --j) {
dTable[i][j] = (grid[i][j] == 'X' || colCnt[j] == 1) ? 0 : dTable[i][j + 1] + 1;
gTable[i][j] = (dTable[i][j] * Y >= X) ? j : gTable[i][j + 1];
}
}
return searchSchedule(0, 0);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N >> M;
for (int i = 0; i < N; ++i) { cin >> grid[i]; for (int j = 0; j < M; ++j) colCnt[j] += (grid[i][j] == '.' ? 1 : 0); }
for (int j = 0; j < M; ++j) if (colCnt[j] == 0) return cout << "-1\n", 0;
for (int i = 0; i <= N; ++i) {
for (int j = 0, x = 0; j < M; ++j) fTable[i][j] = x = (colCnt[j] <= i ? j + 1 : x);
}
vector<array<int, 2>> fractions;
fractions.push_back({0, 1});
for (int i = 1; i <= M; ++i) for (int j = 1; j <= N; ++j) if (std::gcd(i, j) == 1) fractions.push_back({i, j});
sort(fractions.begin(), fractions.end(), [](const auto & a, const auto & b) { return a[0] * b[1] < a[1] * b[0]; });
int ansIdx = 0, l = 1, r = fractions.size() - 1;
while (l <= r) {
int mid = (l + r) >> 1; X = fractions[mid][0]; Y = fractions[mid][1];
if (checkThreshold()) { ansIdx = mid; l = mid + 1; }
else r = mid - 1;
}
cout << fractions[ansIdx][0] << "/" << fractions[ansIdx][1] << "\n";
}