# 113學年度資訊讀書會模擬競賽[1] 題解

預期難度 C < D < B = A = E

## pA 一直走經典題的路線不是辦法吧
problem setter: pooh
idea: fatman
題解: fatman
first AC:

### Subtask 1

暴力人

複雜度:$O(QN)$

### Subtask 2

就是[原題](https://zerojudge.tw/ShowProblem?problemid=i201)，離線，樹壓平做掃描線(按照最深碰到的深度sort)，每次做一次區間詢問

複雜度:$O(Q \log Q + Q \log N)$

### Subtask 3

樹壓平直接做

複雜度:$O(N + Q \log N)$

### Subtask 4

@cot7302 的資結爛作法，直接開二維線段樹，一維是深度，另一維是dfs序，空間是$O(N \log^2 N)$

複雜度:$O(N \log^2 N)$

### Subtask 5

操作分塊

發現一起離線很賺，因為只要$O((N + Q) \log N)$ 就好，那就每$B$ 個做一次離線，然後這$B$ 次裡面的修改先不要算(修改會拆成兩個:修改為原本的值/修改為新的值)，先算完固定的，再來暴力算這次的修改

這樣複雜度是 $O(\frac{Q}{B} ((N + B) \log N + \log \frac{Q}{B}) + \frac{Q}{B} B^2)$，$B$ 取$\sqrt Q$ 最好

複雜度:$O(Q \log Q + N\sqrt Q + Q \sqrt Q)$

空間:$O(N + Q)$

## pB 施竣耀與開心水族箱
problem setter: 餘切
idea: pooh說要出子樹眾數詢問
題解: 餘切
first AC:


:::spoiler 範測是誰
CSES樹
:::

### Subtask 1
暴力，時間複雜度：$O(NQ)$。

### Subtask 2
很明顯可行的區間只有$O(N)$個，直接預處理這些區間，時間複雜度$O(N \log N + Q)$。

### Subtask 3
可能你不想觀察，所以你就砸莫隊，但是其實沒人驗過莫隊會不會過就是了。

### Subtask 4
你從Subtask 2知道可行的區間只有$O(N)$個，然後你就可以觀察到可行區間的上界是$\frac{N}{2}$，實際上可行區間的數量就是$\frac{N}{2}$個（證明留給讀者，或是可以想想我們怎麼生測資的）。
第二個觀察是，這些可行區間兩兩包含或不相交，所以可以蓋出一棵樹。
蓋完樹之後就快樂啟發式合併就做完了。
時間複雜度：$O(N (\log N)^2 + Q)$。

:::spoiler code:

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& V) {
    for (auto& x : V) is >> x;
    return is;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vec<int> A(n);
    cin >> A;
    string S; cin >> S;
    int cnt{};
    vec<vec<int>> G(n / 2);
    vec<pair<int, int>> LR(n / 2);
    vec<int> id(n);
    {
        vec<int> st, tk;
        for (int i = 0; i < n; i++) {
            if (!empty(st) && S[st.back()] == '(' && S[i] == ')') {
                while (!empty(tk) && LR[tk.back()].first > st.back()) {
                    int j = tk.back();
                    G[cnt].emplace_back(j);
                    tk.pop_back();
                }
                LR[cnt] = {st.back(), i};
                id[st.back()] = cnt;
                id[i] = cnt;
                st.pop_back();
                tk.emplace_back(cnt++);
            }
            else {
                st.emplace_back(i);
            }
        }
    }
    vec<int> ans(n / 2);
    auto f = [&](auto&& f, int x) -> pair<map<int, int>, set<pair<int, int>>> {
        map<int, int> mp;
        set<pair<int, int>> st;
        {
            auto [L, R] = LR[x];
            mp[A[L]] += 1;
            mp[A[R]] += 1;
            for (auto [y, c] : mp)
                st.emplace(c, -y);
        }
        for (auto to : G[x]) {
            auto [tm, ts] = f(f, to);
            if (size(tm) > size(mp))
                swap(tm, mp), swap(ts, st);
            for (auto [c, y] : ts) {
                y = -y;
                st.erase({mp[y], -y});
                mp[y] += c;
                st.emplace(mp[y], -y);
            }
        }
        auto [c, y] = *begin(st);
        ans[x] = -y;
        return {move(mp), move(st)};
    };
    f(f, cnt - 1);
    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        l -= 1, r -= 1;
        cout << ans[id[l]] << '\n';
    }
}

:::

## pC 萬物理論
problem setter: pooh
idea: pooh
題解: pooh
first AC: dnnnda at 18:29:46

### Subtask 1
你就暴力看看每一句話有沒有牴觸，反正限制很少怎麼暴力怎麼過
$O(f(K) + \text{poly}(N))$

### Subtask 2
你開 $KN$ 個點做擴展域 DSU，時間 $O(NK \alpha(NK) + QK)$

**這題我沒有寫暴力驗過**

### Subtask 3
你發現種類本質上就是一種 potential, 然後 potential 可以在 dsu 上維護 (因為她可以接受合併與壓縮)，因此你就做一個帶 potential 的 dsu。

$O(N \alpha (N) + Q)$

:::spoiler Code :

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int SIZE = 1e6 + 5;
int MOD;

int dsu[SIZE], potential[SIZE];

void init(int N){
    for (int i = 1; i <= N; i++){
        dsu[i] = -1;
        potential[i] = 0;
    }
    return;
}

int find_rt(int a){
    if(dsu[a] < 0)
        return a;
    int rt = find_rt(dsu[a]);
    potential[a] = (potential[dsu[a]] + potential[a]) % MOD;
    return dsu[a] = rt;
}

bool merge(int a, int b, int delta){
    int rt_a = find_rt(a), rt_b = find_rt(b);
    delta = (delta + potential[a] - potential[b] + MOD) % MOD;
    if(rt_a == rt_b)
        return delta == 0;
    if(dsu[rt_a] > dsu[rt_b])
        swap(rt_a, rt_b), delta = (MOD - delta) % MOD;
    potential[rt_b] = delta;
    dsu[rt_a] += dsu[rt_b];
    dsu[rt_b] = rt_a;
    return 1;
}

int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    int N, K, Q;
    cin >> N >> K >> Q;
    init(N);
    bool detrue = 0;
    MOD = K;
    for (int d, x, y; Q--;){
        cin >> x >> y >> d;
        detrue |= !merge(x, y, d);
    }
    cout << (detrue ? "detrue" : "no detrue")<< '\n';
}

:::

或著直接建圖跑 dfs，沒差，就我忘記有這個要卡，對不起。

## pD pooh 的老題
problem setter: pooh
idea: pooh for ver. 1, cot for ver.2, pyt for 讓我們亂搞一個無意義的加強
題解: pooh
first AC: baocoder613 at 18:47:11

### Subtask 1
直接用調和級數那個篩去暴力算
$O(N \log N)$

### Subtask 2
$d(N)$ 是積性函數，用線性篩
$O(N)$

### Subtask 3

好壞喔 pyt，我們絕對不是在他亂講這句話以後才搞出這一題的。

首先性質 1 是 $\sum_{i=1}^N d(N) = \sum_{i=1}^N \lfloor \frac N i \rfloor$，因為 $\lfloor \frac N i \rfloor$ 其實就是 $1 \sim N$ 裡有多少人的因數有 $i$。

然後這個人可以數論分塊算

最後這個函數是單調遞增的，所以可以二分搜。

$O(\sqrt N \log N)$
:::spoiler Code:

#include <bits/stdc++.h>
#define uwu return 0;
using namespace std;

const long long LLMAX = 1e10 + 5;

long long tar;

bool eval(long long ll){
    long long ans = 0, tmp = 0;
    for (long long i = 1; i * i <= ll; i++){
        ans += ll / i;
        tmp = ll / i;
    }
    for (long long i = 1; i < tmp; i++){
        ans += i * ((ll / i) - (ll / (i + 1)));
    }
    return ans >= tar;
}

int main(){
    cin >> tar;
    long long L = 0, R = LLMAX, M;
    while(L < R){
        M = (L + R) / 2;
        if(eval(M))
            R = M;
        else
            L = M + 1;
    }
    cout << L << '\n';
    uwu
}

:::

## pE gdz problem
problem setter: pooh
idea: 餘切 for 離線版與會過的分塊板、pooh for 在線持久化線段樹板
題解: pooh
first AC:

### Subtask 1
離散化以後暴力
$O(N \log N + NQ)$

### Subtask 2
答案是 0，想怎樣

$O(N + Q)$

### Subtask 3
枚舉每個值看他在這個區間出現幾次
$O(\max(a)(N + Q))$

### Subtask 4
分塊!
還記得區間眾數那個分塊嗎 (不記得的話去 TIOJ 找我的校培簡報)，同理除了整塊的答案以外，散塊的人才有可能是候選人，所以你就先把整塊的答案暴力維護好，然後去看散塊每個人是不是答案的。

$O(\frac {N^2} B + QB) = O(N\sqrt Q)$

### Subtask 5
現在考慮離線的話你會做嗎，你發現這就會是一個掃描線可以解決的問題，蓋一顆區間 max 的線段數，每掃到一個值你就幫這個值上一次出現的地方改值為這個值，然後掃到一個詢問的右界你就在這棵線段樹上面 query(l, r)，這樣總複雜度就是 $O((N + Q) \log N)$ 的。

接著你發現在分塊的時候你一開始算整塊的答案其實是離線的，因此你就掃描線做他。
$O((\frac N B)^2 \log N + QB)$，取 $B = (\frac {N^2 \log N} Q)^{1/3}$ 時最佳，為 $O({(NQ)}^{2/3} \log^{1/3}N)$

或著是你很暴力直接做持久化線段樹，$O(Q \log N)$

:::spoiler 主席樹 ver.

#include <bits/stdc++.h>
#define uwu return 0;
using namespace std;

const int SIZE = 1e6 + 5, LOGN = 25;

int a[SIZE], rtbyr[SIZE];

int cnt = 0;

struct node{
    int l = 0, r = 0, val = 0;
};

node SEGTree[SIZE * LOGN];

#define rt SEGTree[id]
#define prev_rt SEGTree[prev_id]

void cpy(int id, int prev_id){
    rt.l = prev_rt.l, rt.r = prev_rt.r, rt.val = prev_rt.val;
    return;
}

int modify(int prev_id, int pos, int n_val, int L, int R){
    if(!pos)
        return prev_id;

    int id = ++cnt;
    cpy(id, prev_id);
    
    rt.val = max(rt.val, n_val);

    if(L == R)
        return id;
    
    int M = (L + R) / 2;
    
    if(pos <= M)
        rt.l = modify(rt.l, pos, n_val, L, M);
    else
        rt.r = modify(rt.r, pos, n_val, M + 1, R);

    return id;
}

int query(int id, int ql, int qr, int L, int R){
    if(!id)
        return 0;

    if(ql <= L && R <= qr)
        return rt.val;

    int M = (L + R) / 2;

    if(qr <= M)
        return query(rt.l, ql, qr, L, M);
    if(ql > M)
        return query(rt.r, ql, qr, M + 1, R);

    return max(query(rt.l, ql, M, L, M), query(rt.r, M + 1, qr, M + 1, R));
}

#undef rt
#undef prev_rt

int N, Q;

vector<int> discrete;

int pos[SIZE];

int get_id(int x){
    return lower_bound(discrete.begin(), discrete.end(), x) - discrete.begin();
}

void init(){
    cin >> N;
    for (int i = 1; i <= N;i++){
        cin >> a[i];
        discrete.push_back(a[i]);
    }
    sort(discrete.begin(), discrete.end());
    rtbyr[0] = ++cnt;
    for (int i = 1; i <= N;i++){
        rtbyr[i] = modify(rtbyr[i - 1], pos[get_id(a[i])], a[i], 1, N);
        pos[get_id(a[i])] = i;
    }
    return;
}

int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    init();
    cin >> Q;
    int l, r, prev_ans = 0;
    while(Q--){
        cin >> l >> r;
        l ^= prev_ans, r ^= prev_ans;
        prev_ans = query(rtbyr[r], l, r, 1, N);
        cout << prev_ans << '\n';
    }
    uwu
}

:::

:::spoiler 分塊 ver.

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& V) {
    for (auto& x : V) is >> x;
    return is;
}

struct seg_tree {
    int n;
    vector<int> tr;
    seg_tree(int n) : n(n), tr(n * 2, -1) {}

    void set(int i, int v) {
        tr[i += n] = v;
        for (; i /= 2; )
            tr[i] = max(tr[i * 2 + 0], tr[i * 2 + 1]);
    }

    int query(int l, int r) const {
        int ret{-1};
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) ret = max(ret, tr[l++]);
            if (r & 1) ret = max(ret, tr[--r]);
        }
        return ret;
    }
};

struct Magic {
    static inline int B = 1'024;
    int n, nn;
    const vector<int>& arr;
    vector<int> pre, nxt, ans;

    Magic(const vector<int>& a) : n(size(a)), nn(n / B), arr{a}, pre(n, -1), nxt(n, n), ans(nn * nn) {
        const int N = *max_element(begin(arr), end(arr)) + 1;
        vector<int> pos(N, -1);
        seg_tree seg(n);
        for (int i = 0; i < n; i++) {
            if (pos[arr[i]] != -1) {
                int j = pos[arr[i]];
                pre[i] = j;
                nxt[j] = i;
                seg.set(j, arr[i]);
            }
            pos[arr[i]] = i;
            if (i % B == B - 1) {
                int r = i / B;
                for (int j = 0; j < i; j += B) {
                    int l = j / B;
                    ans[l * nn + r] = seg.query(j, i + 1);
                }
            }
        }
    }

    int brute_force(int l, int r, int rr) const {
        int ret{-1};
        for (int i = l; i < r; i++)
            if (nxt[i] < rr) ret = max(ret, arr[i]);
        return ret;
    }

    int brute_force_reversed(int l, int r, int ll) const {
        int ret{-1};
        for (int i = l; i < r; i++)
            if (pre[i] >= ll) ret = max(ret, arr[i]);
        return ret;
    }

    int query(int l, int r) const {
        int lb = (l + B - 1) / B, rb = r / B;
        if (lb >= rb) return brute_force(l, r, r);
        int ret = ans[lb * nn + rb - 1];
        return max({brute_force(l, lb * B, r), ret, brute_force_reversed(rb * B, r, l)});
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    vec<int> A(n);
    cin >> A;
    auto D = A;
    sort(ALL(D));
    D.resize(unique(ALL(D)) - begin(D));
    for (auto& x : A)
        x = lower_bound(ALL(D), x) - begin(D);
    int q; cin >> q;
    Magic::B = max<long double>(1, cbrt((long double)2 * n / q * n * log2(n)));
    Magic ds{A};
    int ans{};
    while (q--) {
        int l, r; cin >> l >> r;
        l ^= ans, r ^= ans;
        l -= 1;
        int i = ds.query(l, r);
        ans = (i == -1 ? 0 : D[i]);
        cout << ans << '\n';
    }
}

:::

bonus : 如果不用線段樹你會做嗎?