分治有普通分治和 CDQ 分治，主要是將問題分成規(guī)模相近的兩個(gè)子問題，再探究子問題之間的關(guān)系。分治優(yōu)化的點(diǎn)是，他將一個(gè)問題拆成了總和為 \(n \log n\) 的若干問題，每個(gè)問題都比原問題更好解決。序列分治一般探究兩個(gè)區(qū)間之間的關(guān)系，而分治不僅可以在普通的維度上分治，還可以對時(shí)間分治。整體二分也是一種分治。以上說的算法模板要十分熟悉。

P6406 Norma

分治模板題，很暴力的分討+拆貢獻(xiàn)，沒什么好說的。

#define int long long

const int N = 5e5 + 7;
const long long mod = 1e9;

int n, a[N], ans = 0;
long long s1[N][2], s2[N][2], s3[N][2];

void alison(int l, int r) {
    if (l == r) {
        (ans += (a[l] * a[l] % mod)) %= mod;
        return ;
    }
    if (l + 1 == r) {
        (ans += (a[l] * a[l] % mod + a[r] * a[r] % mod + 2ll * a[l] * a[r] % mod) % mod) %= mod;
        return ;
    }
    int mid = l + r >> 1;
    for (int i = mid; i <= r; i ++)
        for (int j = 0; j < 2; j ++)
            s1[i][j] = s2[i][j] = s3[i][j] = 0;
    int mn = 2e18, mx = -2e18, j = mid, k = mid;
    for (int i = mid + 1; i <= r; i ++) {
        mn = min(mn, a[i]), mx = max(mx, a[i]);
        s1[i][0] = (s1[i - 1][0] + mn * (i - mid) % mod) % mod, s1[i][1] = (s1[i - 1][1] + mn) % mod;
        s2[i][0] = (s2[i - 1][0] + mx * (i - mid) % mod) % mod, s2[i][1] = (s2[i - 1][1] + mx) % mod;
        s3[i][0] = (s3[i - 1][0] + mn * mx % mod * (i - mid) % mod) % mod, s3[i][1] = (s3[i - 1][1] + mn * mx % mod) % mod;
    }
    debugArr2(s1, mid + 1, r, 0, 1);
    debugArr2(s2, mid + 1, r, 0, 1);
    debugArr2(s3, mid + 1, r, 0, 1);
    mn = 2e18, mx = -2e18;
    for (int i = mid; i >= l; i --) {
        mn = min(mn, a[i]), mx = max(mx, a[i]);
        while (j < r && a[j + 1] > mn) j ++;
        while (k < r && a[k + 1] < mx) k ++;
        int w1 = min(j, k), w2 = max(j, k);
        if (w1 > mid) (ans += mn * mx % mod * (((mid + 1) - i + 1 + w1 - i + 1) * (w1 - mid) / 2 % mod) % mod) %= mod;
        debug(mn * mx % mod * (((mid + 1) - i + 1 + w1 - i + 1) * (w1 - mid) / 2 % mod) % mod);
        if (j < k) (ans += mx * ((s1[k][0] - s1[j][0] + mod) % mod + (mid - i + 1) * (s1[k][1] - s1[j][1] + mod) % mod) % mod) %= mod;
        if (k < j) (ans += mn * ((s2[j][0] - s2[k][0] + mod) % mod + (mid - i + 1) * (s2[j][1] - s2[k][1] + mod) % mod) % mod) %= mod;
        if (w2 < r) (ans += (s3[r][0] - s3[w2][0] + mod) % mod + (mid - i + 1) * (s3[r][1] - s3[w2][1] + mod) % mod) %= mod;
        debug(i, j, k, w1, w2, ans);
    }
    debug(l, r, ans);
    alison(l, mid), alison(mid + 1, r);
}

void solve() {
    n = read();
    for (int i = 1; i <= n; i ++)
        a[i] = read();
    alison(1, n);
    cout << ans << '\n';
}

QOJ 8527 Power Divisions

首先樸素 DP 十分 naive，后續(xù)的分治也比較套路，難點(diǎn)主要在中間的尋找區(qū)間，而不是分治，不細(xì)講。

void alison(int l, int r) {
    if (l == r) return f[l] += f[l - 1], void();
    int mid = l + r >> 1;
    alison(l, mid);
    int sum = 0; rx[0] = mid;
    for (int i = mid + 1; i <= r; i ++) {
        (sum += pw[a[i]]) %= mod;
        rx[sum] = i;
    }
    sum = 0; lx[0] = mid + 1;
    for (int i = mid; i >= l; i --) {
        (sum += pw[a[i]]) %= mod;
        lx[sum] = i;
    }
    sum = 0; set <int> bs; int mx = 0;
    for (int i = mid; i >= l; i --) {
        (sum += pw[a[i]]) %= mod; int tmp = a[i];
        while (bs.find(tmp) != bs.end()) bs.erase(tmp), tmp ++;
        bs.insert(tmp); chkMx(mx, tmp); int tar = (pw[mx + 1] - sum + mod) % mod;
        if (rx.count(tar) && rx[tar] != i) f[rx[tar]] += f[i - 1];
    }
    sum = 0; mx = 0; bs.clear();
    for (int i = mid + 1; i <= r; i ++) {
        (sum += pw[a[i]]) %= mod; int tmp = a[i];
        while (bs.find(tmp) != bs.end()) bs.erase(tmp), tmp ++;
        bs.insert(tmp); chkMx(mx, tmp); int tar = (pw[mx + 1] - sum + mod) % mod;
        if (lx.count(tar) && tar != sum && lx[tar] != i) f[i] += f[lx[tar] - 1];
    }
    lx.clear(), rx.clear();
    alison(mid + 1, r);
}

UOJ612 飲食區(qū)

觀察刪除操作，發(fā)現(xiàn)完全沒用，現(xiàn)在只有加點(diǎn)和查詢操作。考慮樸素的做法，我們二分找第 \(k\) 個(gè)位置的操作點(diǎn)，因此考慮整體二分，比較板。

CF603E Pastoral Oddities

前面第一個(gè)難點(diǎn)就是觀察到充要條件，但這和分治沒啥關(guān)系，不提。這里需要注意到由于偶數(shù)連通塊的特殊性，答案是單調(diào)的，因此可以整體二分。我們對于那些在這次詢問區(qū)間中一定存在或者不存在的邊提前放入并查集中，然后考慮二分值域，從左往右依次加入邊并進(jìn)行合并，然后處理必然存在的邊這里有一個(gè)分治趣點(diǎn)：由于 \(ql, qr\) 和 \(vl, vr\) 都只和分治層數(shù)相關(guān)，我們枚舉 \(qr - ql + 1\) 和 \(vr - vl + 1\) 的時(shí)間復(fù)雜度都是 \(\mathcal{O}(n\log n)\) 的。

P3206 [HNOI2010] 城市建設(shè)

漸入佳境。

這題的重點(diǎn)是考察對于一個(gè)區(qū)間 \([l, r]\)，那些固定的邊和不固定的邊，我們拿這些邊跑 Kruskal，哪些是必要的，哪些完全不要的，哪些是不確定的。如果不確定的邊量級為 \(\mathcal{O}(len)\)，那么時(shí)間復(fù)雜度就是可以接受的。這個(gè)問題就與分治無關(guān)了，我們考慮類似于尋找必要條件，我們先對靜態(tài)邊跑一邊 Kruskal，再對動(dòng)態(tài)邊縮點(diǎn)后的圖跑 Kruskal，剩下來的那些邊容易發(fā)現(xiàn)是 \(\mathcal{O}(k)\) 量級的。

QOJ10706 Red-Blue MST

這題是 WQS 二分和整體二分的完美結(jié)合，前提是要對 WQS 二分足夠熟悉先，我沒這個(gè)前提，我先撤退了。

P5163 WD 與地圖

首先，可以時(shí)間倒流，從刪邊改成進(jìn)行加邊。考慮每一條邊出現(xiàn)在強(qiáng)連通分量的時(shí)間節(jié)點(diǎn)，如果我們能算出這個(gè)，我們就可以使用線段樹合并來完成接下來的查詢，于是問題的關(guān)鍵是如何求出每條邊出現(xiàn)在強(qiáng)連通分量中的時(shí)間。先考慮樸素的，我們對每條邊，二分出現(xiàn)的時(shí)間節(jié)點(diǎn)，然后把前 \(x\) 條邊插入進(jìn)圖中，得到強(qiáng)連通分量的情況，然后查看這條邊是否出現(xiàn)在強(qiáng)連通分量中即可。考慮整體二分，假設(shè)當(dāng)前對于 \([ql, qr]\) 這些邊，他們變成強(qiáng)連通分量的時(shí)間節(jié)點(diǎn)在 \([tl, tr]\) 中，樸素的，考慮先提前處理好 \([1, tl - 1]\) 的縮點(diǎn)情況，然后對 \([tl, mid]\) 這些邊在縮點(diǎn)后的圖上跑一邊 Tarjan，對于在強(qiáng)連通內(nèi)部的邊分到 \([tl, mid]\)，否則分到 \([mid + 1, tr]\)。

P3350 [ZJOI] 旅行者

網(wǎng)格圖分治，本質(zhì)上其實(shí)類似于貓樹，每次選擇一條分割邊，將經(jīng)過這條分割邊的可能的最短路全部處理出來，再分治那些不一定經(jīng)過這條分割邊的詢問。時(shí)間復(fù)雜度是 \(\mathcal{O}(S \sqrt{S} \log S)\) 的，證明比較科幻。

P6976 Distance on Triangulation

和上一道題類似，我們每次選擇一條多邊形的對角線，使得這個(gè)圖能夠被分成均勻的兩部分，然后我們只需要關(guān)注這條對角線的兩個(gè)端點(diǎn)到其他詢問的距離即可。分治的處理那些最短路和對角線可能不相交的詢問。

事實(shí)上對于邊呈現(xiàn)笛卡爾樹的那種圖，我們都可以使用三角剖分分治來解決，大概是你把序列當(dāng)成一個(gè)環(huán)，在環(huán)上做分治即可。

P5044 [IOI2018] meetings

這一題比較特別，是一類笛卡爾樹（最值）分治，我們考慮對當(dāng)前區(qū)間的最大值為分界點(diǎn)。考慮暴力 DP，設(shè) \(f_{l, r}\) 表示區(qū)間 \([l,r]\) 的最小代價(jià)，那么我們考慮決策點(diǎn)在最大值左邊還是右邊就可以進(jìn)行轉(zhuǎn)移了。放到分治上來，如果當(dāng)前我們已經(jīng)求出所有 \(f_{i, mid}\) 和 \(f_{mid, i}\)，那么我們考慮如何合并這兩個(gè) DP 值。同暴力轉(zhuǎn)移，我們能求出 \(f_{l, i}\) 和 \(f_{i, r}\)，但是時(shí)間復(fù)雜度是 \(\mathcal{O}(n^2)\) 的。剩下就和分治沒啥關(guān)系了，我們發(fā)現(xiàn)這兩個(gè)值是單調(diào)的，因此二分出分界點(diǎn)之后，我們可以進(jìn)行一個(gè)區(qū)間加法，區(qū)間賦值等差數(shù)列，線段樹即可。