Rollback

Ngăn xếp lịch sử

Mỗi thao tác sửa đổi đẩy vào ngăn xếp đủ thông tin để đảo ngược nó: thêm vào cuối thì nhớ độ dài đã thêm, xóa thì nhớ phần đã xóa, gán ô thì nhớ giá trị cũ. Hoàn tác lấy đỉnh ngăn xếp và làm phép ngược. Mốc lưu trạng thái chỉ là kích thước ngăn xếp tại lúc đặt mốc; quay về mốc là hoàn tác cho tới khi ngăn xếp còn đúng kích thước đó.

Chi phí hoàn tác bằng chi phí của chính thao tác bị hủy, nên tổng thời gian vẫn tuyến tính theo tổng thao tác. Điều này chỉ đúng khi hoàn tác theo thứ tự ngược (ngăn xếp); muốn hủy một thao tác ở giữa thì cần cấu trúc khác.

Ví dụTrình Soạn Thảo Có Hoàn Tác

Đề. Chuỗi ban đầu rỗng, $q \le 10^5$ thao tác: nối xâu vào cuối, xóa $k$ ký tự cuối, in ký tự thứ $k$, hoàn tác thao tác sửa gần nhất.

Lời giải. Giữ xâu hiện tại s và một ngăn xếp lịch sử; mỗi thao tác sửa đẩy vào đúng thông tin để làm ngược nó. Nối thêm $w$ thì nhớ độ dài $|w|$: hoàn tác là cắt bớt chừng ấy ký tự. Xóa $k$ ký tự cuối thì nhớ chính $k$ ký tự đó: hoàn tác là nối lại. Thao tác in không sửa gì nên không đẩy vào lịch sử, và lệnh hoàn tác luôn nhắm vào thao tác sửa gần nhất còn lại.

Bước 1: ghi lịch sử. hist chứa cặp (độ dài, xâu). Lần nối ghi (|w|, ""); lần xóa ghi (0, phần bị xóa). Độ dài 0 là dấu hiệu của lần xóa, vì xâu nối vào luôn khác rỗng. Lệnh xóa lấy substr trước khi resize; làm ngược thứ tự thì phần bị xóa đã mất.

hist.push_back({0, s.substr(s.size() - k)});
s.resize(s.size() - k);

Bước 2: hoàn tác. Lấy bản ghi trên cùng: có độ dài thì cắt bớt, không có thì nối lại phần đã xóa.

pair<int, string> h = hist.back();
hist.pop_back();
if (h.first) s.resize(s.size() - h.first);
else s += h.second;

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int q;
    cin >> q;
    string s;
    vector<pair<int, string>> hist;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            string w;
            cin >> w;
            s += w;
            hist.push_back({(int)w.size(), ""});
        } else if (t == 2) {
            int k;
            cin >> k;
            hist.push_back({0, s.substr(s.size() - k)});
            s.resize(s.size() - k);
        } else if (t == 3) {
            int k;
            cin >> k;
            cout << s[k - 1] << '\n';
        } else {
            pair<int, string> h = hist.back();
            hist.pop_back();
            if (h.first) s.resize(s.size() - h.first);
            else s += h.second;
        }
    }
}

Input9
1 abc
3 3
2 2
1 xy
3 2
4
1 z
4
3 1

Outputc
x
a

Mỗi ký tự được thêm, xóa, nối lại và cắt đi một số lần bị chặn bởi tổng độ dài các xâu trong input: tổng thời gian tuyến tính theo dữ liệu.

DSU hoàn tác

DSU nén đường đi sửa rất nhiều ô par trong một lần find, khó hoàn tác. Bỏ nén, chỉ hợp theo kích thước: cây luôn cao $O(\log n)$ nên find vẫn $O(\log n)$, và mỗi lần hợp chỉ sửa par[b] cùng sz[a]. Lịch sử là danh sách các cặp $(a, b)$ đã hợp; hoàn tác đặt par[b] = b, sz[a] -= sz[b]. Số thành phần và các đại lượng gộp khác (tổng, cực tiểu) cũng được đặt lại cùng lúc.

Lần hợp không đổi gì (hai đỉnh đã cùng thành phần) thì không đẩy vào lịch sử; mốc vẫn là kích thước ngăn xếp nên quay về mốc vẫn đúng.

Ví dụDSU Có Mốc Khôi Phục

Đề. $n, q \le 2 \cdot 10^5$. Lệnh union u v hợp hai thành phần và in số thành phần; persist đặt mốc; rollback quay về mốc gần nhất, bỏ mốc đó và in số thành phần.

Lời giải. DSU hợp theo kích thước, không nén đường đi, nên mỗi lần hợp chỉ sửa par[b] và sz[a]. Lịch sử là ngăn xếp các cặp $(a, b)$ đã hợp; số thành phần comps cũng đổi theo. Đặt mốc là ghi lại kích thước lịch sử lúc đó; quay về mốc là hoàn tác cho tới khi lịch sử còn đúng kích thước ấy.

Bước 1: tìm gốc không nén. Đi lên tới gốc, không sửa gì. Hợp theo kích thước giữ cây cao không quá $\log_2 n$.

int find(int u) {
    while (par[u] != u) u = par[u];
    return u;
}

Bước 2: hợp có ghi lịch sử. Cùng gốc thì thoát luôn, không đẩy gì; khác gốc thì gắn gốc nhỏ b vào gốc lớn a, giảm comps, đẩy $(a, b)$. Lần hợp vô ích không vào lịch sử, nên mốc (một kích thước) vẫn đúng.

void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a, sz[a] += sz[b], comps--;
    hist.push_back({a, b});
}

Bước 3: hoàn tác về mốc. Làm ngược từng cặp trên cùng. Hoàn tác đúng thứ tự ngược nên mỗi bước khôi phục chính xác trạng thái ngay trước lần hợp đó. marks là ngăn xếp các mốc.

void rollback(int t) {
    while ((int)hist.size() > t) {
        int a = hist.back().first, b = hist.back().second;
        hist.pop_back();
        par[b] = b, sz[a] -= sz[b], comps++;
    }
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5 + 5;
int n, q, comps, par[N], sz[N];
vector<pair<int, int>> hist;

int find(int u) {
    while (par[u] != u) u = par[u];
    return u;
}

void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a, sz[a] += sz[b], comps--;
    hist.push_back({a, b});
}

void rollback(int t) {
    while ((int)hist.size() > t) {
        int a = hist.back().first, b = hist.back().second;
        hist.pop_back();
        par[b] = b, sz[a] -= sz[b], comps++;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    comps = n;
    vector<int> marks;
    while (q--) {
        string op;
        cin >> op;
        if (op == "union") {
            int u, v;
            cin >> u >> v;
            unite(u, v);
            cout << comps << '\n';
        } else if (op == "persist") marks.push_back(hist.size());
        else {
            rollback(marks.back());
            marks.pop_back();
            cout << comps << '\n';
        }
    }
}

Input5 8
union 1 2
persist
union 2 3
union 1 3
persist
union 4 5
rollback
rollback

Output4
3
3
2
3
4

Mỗi lần hợp $O(\log n)$, mỗi lần hoàn tác $O(1)$.

Cây phiên bản: DFS rồi hoàn tác

Khi mỗi phiên bản được tạo từ một phiên bản cũ bất kỳ, các phiên bản tạo thành cây. Nếu được trả lời ngoại tuyến, không cần cấu trúc bền vững: DFS trên cây phiên bản, đi vào đỉnh thì áp dụng thao tác của nó, trả lời truy vấn của nó, duyệt các con, rồi hoàn tác về trạng thái trước khi vào. Mỗi thao tác được áp dụng và hoàn tác đúng một lần.

Cây phiên bản có thể sâu tới số thao tác; dùng ngăn xếp tường minh với hai loại phần tử, “vào đỉnh” và “ra khỏi đỉnh (kèm mốc)”, để khỏi đệ quy sâu.

Ví dụDSU Theo Cây Phiên Bản

Đề. $n, q \le 2 \cdot 10^5$. Thao tác $i$ tạo phiên bản $i$ từ phiên bản $k$: hoặc hợp $u, v$, hoặc giữ nguyên và hỏi $u, v$ có cùng thành phần trong phiên bản $k$ không. Phiên bản gốc là $-1$.

Lời giải. Phiên bản $i$ tạo từ phiên bản $k$, nên các phiên bản tạo thành một cây; dời số lên 1 để phiên bản gốc $-1$ là đỉnh 0. Trả lời ngoại tuyến bằng DFS trên cây đó với DSU hoàn tác của ví dụ trước: vào đỉnh thì áp thao tác của nó (hợp hay hỏi), duyệt các con, rồi hoàn tác về trạng thái trước khi vào. Khi đứng ở đỉnh $v$, DSU đúng bằng phiên bản $v$.

Bước 1: dựng cây phiên bản. Đỉnh $i$ là con của đỉnh $k + 1$.

cin >> tp[i] >> k >> qu[i] >> qv[i];
ch[k + 1].push_back(i);

Bước 2: DFS bằng ngăn xếp. Cây có thể sâu tới $2 \cdot 10^5$ nên dùng ngăn xếp tường minh, chứa hai loại phần tử: {v, 0} với $v \ge 0$ là “vào đỉnh $v$”, {-1, saved} là “ra khỏi một đỉnh” kèm kích thước lịch sử trước khi vào nó. Vào đỉnh thì đẩy lệnh ra trước các con: ngăn xếp lấy phần tử sau cùng trước, nên mọi con (cùng cả cây con) xong rồi mới tới lệnh ra của $v$.

int v = st.back().first, mark = st.back().second;
st.pop_back();
if (v < 0) {
    rollback(mark);
    continue;
}
int saved = hist.size();
if (v > 0) {
    if (tp[v] == 0) unite(qu[v], qv[v]);
    else ans[v] = find(qu[v]) == find(qv[v]);
}
st.push_back({-1, saved});
for (int c : ch[v]) st.push_back({c, 0});

Lệnh hỏi không sửa DSU, nên phiên bản $v$ giống phiên bản cha của nó, đúng là phiên bản $k$ mà đề hỏi.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5 + 5;
int n, q, par[N], sz[N], tp[N], qu[N], qv[N], ans[N];
vector<int> ch[N];
vector<pair<int, int>> hist;

int find(int u) {
    while (par[u] != u) u = par[u];
    return u;
}

void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a, sz[a] += sz[b];
    hist.push_back({a, b});
}

void rollback(int t) {
    while ((int)hist.size() > t) {
        int a = hist.back().first, b = hist.back().second;
        hist.pop_back();
        par[b] = b, sz[a] -= sz[b];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 0; i < n; i++) par[i] = i, sz[i] = 1;
    for (int i = 1; i <= q; i++) {
        int k;
        cin >> tp[i] >> k >> qu[i] >> qv[i];
        ch[k + 1].push_back(i);
    }
    vector<pair<int, int>> st = {{0, 0}};
    while (!st.empty()) {
        int v = st.back().first, mark = st.back().second;
        st.pop_back();
        if (v < 0) {
            rollback(mark);
            continue;
        }
        int saved = hist.size();
        if (v > 0) {
            if (tp[v] == 0) unite(qu[v], qv[v]);
            else ans[v] = find(qu[v]) == find(qv[v]);
        }
        st.push_back({-1, saved});
        for (int c : ch[v]) st.push_back({c, 0});
    }
    for (int i = 1; i <= q; i++)
        if (tp[i] == 1) cout << ans[i] << '\n';
}

Input4 7
0 -1 0 1
0 0 1 2
1 1 0 2
1 0 0 2
0 -1 2 3
1 4 2 3
1 1 0 3

Output1
0
1
0

Mỗi thao tác hợp làm một lần và hoàn tác một lần: $O(q \log n)$.

Kết nối động ngoại tuyến

Cạnh được thêm và xóa xen các truy vấn: DSU không xóa được. Nhưng mỗi cạnh sống trong một khoảng thời gian $[l, r)$ (từ lúc thêm tới lúc xóa, hoặc tới cuối). Dựng cây phân đoạn trên trục thời gian, rải mỗi cạnh vào $O(\log T)$ nút phủ đúng khoảng sống của nó. DFS cây phân đoạn: vào nút thì hợp mọi cạnh của nút, xuống hai con, ra thì hoàn tác. Tại lá $t$, DSU chứa đúng các cạnh sống ở thời điểm $t$. Tổng $O(T \log T \log n)$.

Truy vấn nào cũng được miễn DSU trả lời được: số thành phần, hai đỉnh có nối không, tổng trọng số thành phần.

Ví dụMạng Lưới Theo Thời Gian

Đề. $n, m \le 3 \cdot 10^5$. Các thao tác thêm cạnh, xóa cạnh, và ? in số thành phần.

Lời giải. Mỗi thao tác là một thời điểm $t = 0..m-1$. Cạnh thêm ở $s$ và xóa ở $t$ sống trên $[s, t - 1]$; cạnh còn tới cuối sống tới $m - 1$. Rải mỗi khoảng sống vào các nút phủ của cây phân đoạn thời gian, rồi DFS: vào nút thì hợp mọi cạnh của nút, xuống hai con, ra thì hoàn tác. Tới lá $t$, DSU chứa đúng các cạnh sống ở thời điểm $t$. DSU hoàn tác như các ví dụ trước; đệ quy chỉ sâu $\log_2 m$ nên không lo tràn ngăn xếp.

Bước 1: khoảng sống. Chuẩn hóa $u < v$ để cùng một cạnh có cùng khóa. start nhớ thời điểm thêm của các cạnh đang sống. Gặp - thì có khoảng $[start, t - 1]$. Sau khi đọc hết, cạnh còn trong start sống tới $m - 1$.

if (u > v) swap(u, v);
if (c == '+') start[{u, v}] = t;
else {
    addEdge(1, 0, m - 1, start[{u, v}], t - 1, {u, v});
    start.erase({u, v});
}

Bước 2: rải cạnh vào cây. Như cập nhật đoạn, đặt cạnh vào $O(\log m)$ nút nằm trọn trong khoảng sống.

void addEdge(int x, int l, int r, int ql, int qr, pair<int, int> e) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        seg[x].push_back(e);
        return;
    }
    int mid = (l + r) / 2;
    addEdge(2 * x, l, mid, ql, qr, e);
    addEdge(2 * x + 1, mid + 1, r, ql, qr, e);
}

Bước 3: DFS và hoàn tác. saved là kích thước lịch sử trước khi vào nút; ở lá ghi comps nếu là câu hỏi.

void dfs(int x, int l, int r) {
    int saved = hist.size();
    for (pair<int, int> e : seg[x]) unite(e.first, e.second);
    if (l == r) {
        if (isQuery[l]) ans[l] = comps;
    } else {
        int mid = (l + r) / 2;
        dfs(2 * x, l, mid);
        dfs(2 * x + 1, mid + 1, r);
    }
    rollback(saved);
}

m == 0 thì không có gì để làm; thoát sớm tránh dựng cây trên đoạn rỗng.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 3e5 + 5;
int n, m, comps, par[N], sz[N], ans[N];
bool isQuery[N];
vector<pair<int, int>> seg[4 * N], hist;

int find(int u) {
    while (par[u] != u) u = par[u];
    return u;
}

void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a, sz[a] += sz[b], comps--;
    hist.push_back({a, b});
}

void rollback(int t) {
    while ((int)hist.size() > t) {
        int a = hist.back().first, b = hist.back().second;
        hist.pop_back();
        par[b] = b, sz[a] -= sz[b], comps++;
    }
}

void addEdge(int x, int l, int r, int ql, int qr, pair<int, int> e) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        seg[x].push_back(e);
        return;
    }
    int mid = (l + r) / 2;
    addEdge(2 * x, l, mid, ql, qr, e);
    addEdge(2 * x + 1, mid + 1, r, ql, qr, e);
}

void dfs(int x, int l, int r) {
    int saved = hist.size();
    for (pair<int, int> e : seg[x]) unite(e.first, e.second);
    if (l == r) {
        if (isQuery[l]) ans[l] = comps;
    } else {
        int mid = (l + r) / 2;
        dfs(2 * x, l, mid);
        dfs(2 * x + 1, mid + 1, r);
    }
    rollback(saved);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    comps = n;
    if (m == 0) return 0;
    map<pair<int, int>, int> start;
    for (int t = 0; t < m; t++) {
        char c;
        cin >> c;
        if (c == '?') {
            isQuery[t] = 1;
            continue;
        }
        int u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        if (c == '+') start[{u, v}] = t;
        else {
            addEdge(1, 0, m - 1, start[{u, v}], t - 1, {u, v});
            start.erase({u, v});
        }
    }
    for (pair<pair<int, int>, int> e : start) addEdge(1, 0, m - 1, e.second, m - 1, e.first);
    dfs(1, 0, m - 1);
    for (int t = 0; t < m; t++)
        if (isQuery[t]) cout << ans[t] << '\n';
}

Input6 9
?
+ 1 2
+ 2 3
?
+ 1 3
- 2 3
?
- 1 3
?

Output6
4
4
5

Mỗi cạnh nằm ở $O(\log m)$ nút, mỗi lần hợp $O(\log n)$: tổng $O(m \log m \log n)$.

DSU giữ chẵn lẻ: kiểm hai phía theo thời gian

Mỗi đỉnh lưu thêm xr[v], chẵn lẻ của nó so với cha. find trả về gốc cùng tổng XOR trên đường lên gốc, tức màu tương đối với gốc. Thêm cạnh $(u, v)$: nếu cùng gốc mà cùng màu thì đồ thị có chu trình lẻ, không còn hai phía; khác gốc thì nối hai gốc với xr sao cho $u$, $v$ khác màu. Hoàn tác đặt lại cả xr.

Trên cây phân đoạn thời gian, một khi nút đã có chu trình lẻ thì mọi lá bên dưới đều không hai phía, khỏi đi xuống nữa.

Ví dụKiểm Tra Hai Màu Theo Ngày

Đề. $n, q \le 10^5$. Mỗi ngày bật hoặc tắt một cạnh; sau mỗi ngày in YES nếu đồ thị tô được hai màu.

Lời giải. Như ví dụ trước, mỗi cạnh có khoảng ngày sống, rải vào cây phân đoạn thời gian. DSU lưu thêm xr[v], chẵn lẻ của $v$ so với cha, để biết màu của mỗi đỉnh so với gốc. Hợp một cạnh mà hai đầu đã cùng thành phần và cùng màu nghĩa là có chu trình lẻ. Khi một nút gặp chu trình lẻ, mọi ngày trong đoạn của nút đều chứa cạnh đó, nên cả đoạn là NO và khỏi đi xuống.

Bước 1: gốc kèm màu. find(u) trả về gốc cùng XOR các xr trên đường lên, tức màu của $u$ so với gốc.

pair<int, int> find(int u) {
    int x = 0;
    while (par[u] != u) x ^= xr[u], u = par[u];
    return {u, x};
}

Bước 2: hợp kiểm hai màu. Cùng gốc thì cạnh hợp lệ khi và chỉ khi hai màu khác nhau. Khác gốc thì gắn gốc nhỏ vào gốc lớn và chọn xr của gốc nhỏ là a.second ^ b.second ^ 1, để màu của $u$ và $v$ khác nhau sau khi nối. Lịch sử chỉ cần lưu gốc nhỏ b: lúc hoàn tác, cha của nó chính là gốc lớn.

bool unite(int u, int v) {
    pair<int, int> a = find(u), b = find(v);
    if (a.first == b.first) return a.second != b.second;
    if (sz[a.first] < sz[b.first]) swap(a, b);
    par[b.first] = a.first, xr[b.first] = a.second ^ b.second ^ 1, sz[a.first] += sz[b.first];
    hist.push_back(b.first);
    return 1;
}

Bước 3: cắt sớm khi hỏng. Gặp cạnh hỏng thì dừng và gán NO cho mọi ngày trong đoạn; các cạnh đã hợp trước đó vẫn được hoàn tác bởi rollback(saved).

for (pair<int, int> e : seg[x])
    if (!unite(e.first, e.second)) {
        good = 0;
        break;
    }
if (!good)
    for (int t = l; t <= r; t++) ok[t] = 0;

Bước 4: bật tắt. Cặp $(u, v)$ đang có trong start thì lần này là tắt, ngược lại là bật. Ngày $t$ in trạng thái sau thao tác của ngày đó, nên cạnh tắt ở ngày $t$ chỉ sống tới $t - 1$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5 + 5;
int n, q, par[N], sz[N], xr[N];
bool ok[N];
vector<pair<int, int>> seg[4 * N];
vector<int> hist;

pair<int, int> find(int u) {
    int x = 0;
    while (par[u] != u) x ^= xr[u], u = par[u];
    return {u, x};
}

bool unite(int u, int v) {
    pair<int, int> a = find(u), b = find(v);
    if (a.first == b.first) return a.second != b.second;
    if (sz[a.first] < sz[b.first]) swap(a, b);
    par[b.first] = a.first, xr[b.first] = a.second ^ b.second ^ 1, sz[a.first] += sz[b.first];
    hist.push_back(b.first);
    return 1;
}

void rollback(int t) {
    while ((int)hist.size() > t) {
        int b = hist.back();
        hist.pop_back();
        sz[par[b]] -= sz[b], par[b] = b, xr[b] = 0;
    }
}

void addEdge(int x, int l, int r, int ql, int qr, pair<int, int> e) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        seg[x].push_back(e);
        return;
    }
    int mid = (l + r) / 2;
    addEdge(2 * x, l, mid, ql, qr, e);
    addEdge(2 * x + 1, mid + 1, r, ql, qr, e);
}

void dfs(int x, int l, int r) {
    int saved = hist.size();
    bool good = 1;
    for (pair<int, int> e : seg[x])
        if (!unite(e.first, e.second)) {
            good = 0;
            break;
        }
    if (!good)
        for (int t = l; t <= r; t++) ok[t] = 0;
    else if (l == r) ok[l] = 1;
    else {
        int mid = (l + r) / 2;
        dfs(2 * x, l, mid);
        dfs(2 * x + 1, mid + 1, r);
    }
    rollback(saved);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
    map<pair<int, int>, int> start;
    for (int t = 0; t < q; t++) {
        int u, v;
        cin >> u >> v;
        if (start.count({u, v})) {
            addEdge(1, 0, q - 1, start[{u, v}], t - 1, {u, v});
            start.erase({u, v});
        } else start[{u, v}] = t;
    }
    for (pair<pair<int, int>, int> e : start) addEdge(1, 0, q - 1, e.second, q - 1, e.first);
    dfs(1, 0, q - 1);
    for (int t = 0; t < q; t++) cout << (ok[t] ? "YES" : "NO") << '\n';
}

Input4 7
1 2
2 3
1 3
1 3
3 4
1 4
2 4

OutputYES
YES
NO
YES
YES
YES
NO

$O(q \log q \log n)$.