分治

树分治 – 点分治

首先选一个点作为根，把无根树变为有根树，然后递归进行分支（DFS-like）。但是，为了减小复杂度，我们希望在一棵树中递归层数控制到最小，那么这个点的选择就非常的重要。我们选择重心来搞定这个。有了重心，我们的子树大小都不会超过\(n/2\)；计算完了之后，删掉根，并递归子树。所以时间复杂度是优秀的\(O(n\log n)\)。

重心的求法：我们用 \(O(n)\) 的时间来求出以每个点为根的子树大小，然后判断划分出联通块各点最少的点，那么这个点就是重心。

例题：IOI2011 Race，POJ1741:Tree 题解

思路：找到重心，则路径可以表示为经过根的两条子路径。第一遍 DFS 中记录走到每个点的距离和边数，同时统计到距离\(dist\)的最小边数\(sides[dist]\)。答案就是

\[ans=max\{sides[k-dist[i]]+sideSubtree[i]\}\]

一定要统计完答案之后再去用\(sideSubtree\)更新\(sides[]\)数组。

树分治 – 边分治

依旧需要找重心，但是在一些极限环境下（菊花图之类的）就会出锅，复杂度飙升。这个时候可以搞重构树来解决，把一颗菊花图搞成二叉树（建虚点，搞零边权的边）（目前还不怎么懂）

具体可以看这篇文章：https://ksmeow.moe/edge_based_divide_and_conquer/

例题：BZOJ2870

树分治 – 树链剖分

树链剖分是个好用的东西。我们可以第一遍 DFS 可以求出所有的重儿子，第二遍 DFS 的时候优先走重儿子，求时间戳。

对于重链的区间操作，直接暴力时间戳区间操作；对于轻边或混合链，LCA-like 算法可以搞定。

这个洛谷上题好多，不举例了。

CDQ 分治

CDQ 分治是一个神仙的离线算法。老师讲的太快，没看完就切掉了 PPT。

整体二分

功能：对于所有的询问都进行二分来加速。

分块

普通分块

普通的分块最重要的一点就是确定区间长度。确定一个好的区间长度能让时间复杂度大大降低。一般我们使用\(\sqrt{n}\)来作为区间长度。用数组存好左右端点和每个点所属的区块，并预处理必要的信息。

例题：Contest Hunter 4401 – 蒲公英

这道题要求我们维护众数，我们可以先预处理每个两个区块间的众数，然后再每个数搞一个\(vector\)记录数出现的位置，对于暴力的区间，我们可以二分两次并相减得出出现次数。这样就可以解决问题了：

// CH4401.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 40100;
vector<int> poses[MAX_N];
int arr[MAX_N], mapping[MAX_N], lft[MAX_N], tot, rig[MAX_N], cnt[MAX_N], mode[900][900], affiliate[MAX_N];
int find(int x, int l, int r)
{
    return upper_bound(poses[x].begin(), poses[x].end(), r) - lower_bound(poses[x].begin(), poses[x].end(), l);
}
void judge(int x, int l, int r, int &ans, int &ct)
{
    int w = find(x, l, r);
    if (w > ct || (w == ct && x < ans))
        ct = w, ans = x;
}
int query(int l, int r)
{
    int ans = 0, ct = 0;
    int p = affiliate[l], q = affiliate[r];
    if (p == q)
    {
        for (int i = l; i <= r; i++)
            judge(arr[i], l, r, ans, ct);
        return mapping[ans];
    }
    int x = 0, y = 0;
    if (p + 1 <= q - 1)
        x = p + 1, y = q - 1;
    for (int i = l; i <= rig[p]; i++)
        judge(arr[i], l, r, ans, ct);
    for (int i = lft[q]; i <= r; i++)
        judge(arr[i], l, r, ans, ct);
    if (mode[x][y])
        judge(mode[x][y], l, r, ans, ct);
    return mapping[ans];
}
int main()
{
    int n, m, t, len;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]), mapping[++tot] = arr[i];
    sort(mapping + 1, mapping + 1 + n);
    tot = unique(mapping + 1, mapping + 1 + n) - (mapping + 1);
    for (int i = 1; i <= n; i++)
        arr[i] = lower_bound(mapping + 1, mapping + 1 + tot, arr[i]) - mapping, poses[arr[i]].push_back(i);
    t = sqrt(log(n) / log(2) * n);
    len = t ? n / t : n;
    for (int i = 1; i <= t; i++)
        lft[i] = (i - 1) * len + 1, rig[i] = i * len;
    if (rig[t] < n)
        lft[t + 1] = rig[t] + 1, rig[++t] = n;
    for (int i = 1; i <= t; i++)
        for (int j = lft[i]; j <= rig[i]; j++)
            affiliate[j] = i;
    memset(mode, 0, sizeof(mode));
    for (int i = 1; i <= t; i++)
    {
        memset(cnt, 0, sizeof(cnt));
        int ct = 0, ans = 0;
        for (int j = lft[i]; j <= n; j++)
        {
            if (++cnt[arr[j]] > ct || (cnt[arr[j]] == ct && arr[j] < ans))
                ans = arr[j], ct = cnt[arr[j]];
            mode[i][affiliate[j]] = ans;
        }
    }
    int last = 0;
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r), l = (l + last - 1) % n + 1, r = (r + last - 1) % n + 1;
        if (l > r)
            swap(l, r);
        last = query(l, r);
        printf("%d\n", last);
    }
    return 0;
}

莫队算法

对于可以离线的问题，我们考虑询问进行分块。先对每一块内第一个问题进行暴力求解，然后块内的其他问答都用\(O(\sqrt{n})\)的时间搞定转移。非常好用。

例题：BZOJ2038: [2009国家集训队]小Z的袜子(hose)

显然，单纯计算区间内答案式子是：

\[\frac{ans}{{r-l+1 \choose 2}}, \text{其中ans是相同袜子的对数。}\]

对于每一个区块，我们可以维护一个\(num[]\)数组记录每一个颜色的出现次数，然后进行转移时对 ans 进行积累，更新询问答案即可。

// BZ2038.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX_N = 50100;
struct query
{
    ll l, r, id, answerSon, answerDom;
    bool operator<(const query &qy) const { return id < qy.id; }
} queries[MAX_N];

ll ci[MAX_N], n, m, len, btot, num[MAX_N], lft[MAX_N], rig[MAX_N], ans;

bool compare_left(query a, query b) { return a.l < b.l || (a.l == b.l && a.r < b.r); }
bool compare_right(query a, query b) { return a.r < b.r || (a.r == b.r && a.l < b.l); }
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

void change(ll x, ll w)
{
    ans -= num[x] * (num[x] - 1);
    num[x] += w;
    ans += num[x] * (num[x] - 1);
}

void simplify(ll id)
{
    ll d = gcd(queries[id].answerSon, queries[id].answerDom);
    if (!d)
        queries[id].answerSon = 0, queries[id].answerDom = 1;
    else
        queries[id].answerSon /= d, queries[id].answerDom /= d;
}

int main()
{
    scanf("%lld%lld", &n, &m);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &ci[i]);
    for (ll i = 1; i <= m; i++)
        scanf("%lld%lld", &queries[i].l, &queries[i].r), queries[i].id = i;

    len = sqrt(m), btot = m / len;
    sort(queries + 1, queries + 1 + m, compare_left);
    for (ll i = 1; i <= btot; i++)
        lft[i] = (i - 1) * len + 1, rig[i] = i * len;
    if (rig[btot] < m)
        lft[btot + 1] = rig[btot++] + 1, rig[btot] = m;

    for (ll i = 1; i <= btot; i++)
    {
        sort(queries + lft[i], queries + rig[i] + 1, compare_right);
        memset(num, 0, sizeof(num));
        ans = 0;
        // previous interval;
        ll l = queries[lft[i]].l, r = queries[lft[i]].r;
        // process the first query;
        for (ll j = l; j <= r; j++)
            change(ci[j], 1);
        queries[lft[i]].answerSon = ans;
        queries[lft[i]].answerDom = (queries[lft[i]].r - queries[lft[i]].l + 1) * (queries[lft[i]].r - queries[lft[i]].l);
        simplify(lft[i]);

        for (ll j = lft[i] + 1; j <= rig[i]; j++)
        {
            while (l < queries[j].l)
                change(ci[l++], -1);
            while (l > queries[j].l)
                change(ci[--l], 1);
            while (r < queries[j].r)
                change(ci[++r], 1);
            while (r > queries[j].r)
                change(ci[r--], -1);
            if (queries[j].l == queries[j].r)
                queries[j].answerSon = 0, queries[j].answerDom = 1;
            else
            {
                queries[j].answerSon = ans, queries[j].answerDom = (r - l) * (r - l + 1);
                simplify(j);
            }
        }
    }

    sort(queries + 1, queries + 1 + m);
    for (ll i = 1; i <= m; i++)
        printf("%lld/%lld\n", queries[i].answerSon, queries[i].answerDom);
    return 0;
}

树上莫队

把树上问题转换为序列问题，括号序列（欧拉序）可解。例题：SPOJ COT 2