分治算法综合（一）

分治算法中有一些值得探讨的高级专题
比如
$\text{CDQ}$分治，树上分治，整体分治
其中树上分治又被分为点分治，边分治，动态树分治
从这篇博文开始陆续对这些内容做一个补充

点分治

POJ1741

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n, k;

// == Graph definition ==
int M = 0;
class Edge {
public:
    int to, weight;
    Edge *next;
    Edge() {}
    Edge(int to, int w) : to(to), weight(w) {
        next = NULL;
    }
} edges[maxn << 1], *head[maxn];

void initG() {
    M = 0;
    memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
    edges[++M] = Edge(v, w);
    edges[M].next = head[u];
    head[u] = &edges[M];
}
// == Graph finished ==

// == find gravity and get root ==
int sz[maxn];
int sn = n;
int vis[maxn];
int root = 0;
void getRoot(int x, int pa, int& res) {
    sz[x] = 1;
    int maxpart = 0;
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;
        if(vis[y] || y == pa) continue;

        getRoot(y, x, res);
        sz[x] += sz[y];
        maxpart = max(maxpart, sz[y]);
    }
    maxpart = max(maxpart, sn - sz[x]);
    if(maxpart < res) {
        res = maxpart;
        root = x;
    }
}
// == get root finished ==

// == getDep ==
int dep[maxn];

void getDep(int x, int pa, vector<int>& vec) {
    vec.push_back(dep[x]);
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;
        if(y == pa || vis[y]) continue;

        dep[y] = dep[x] + w;
        getDep(y, x, vec);
    }
}
// == getDep finished ==

// == cal(p) ==
inline int cal(int x) {
    vector<int> vec;
    getDep(x, 0, vec);
    sort(vec.begin(), vec.end());

    int sum = 0, i = 0, j = vec.size() - 1;
    while (i < j) {
        if(vec[i] + vec[j] <= k) sum += j - i, i++;
        else j--;
    }
    return sum;
}
// == cal(p) finished ==

// == work ==
void work(int x, int& ans) {
    dep[x] = 0;
    vis[x] = 1;
    ans += cal(x);

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;
        if(vis[y]) continue;

        dep[y] = dep[x] + w;
        ans -= cal(y);

        sn = sz[y];
        root = 0;
        int res = inf;
        getRoot(y, 0, res);

        work(root, ans);
    }
}
// == work finished ==

void init() {
    //
    Set(sz, 0);
    Set(vis, 0);
    sn = n;
    root = 0;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &n, &k) == 2 && n) {
        initG();
        init();

        // input data
        _for(i, 1, n) {
            int x, y, w;
            scanf("%d%d%d", &x, &y, &w);
            add(x, y, w);
            add(y, x, w);
        }
        // input finished

        int res = inf;
        getRoot(1, 0, res);
        int ans = 0;
        work(root, ans);
        printf("%d\n", ans);
    }
}

点分治树状数组统计

$root \leftarrow getRoot(x)$
$\text{find }\textbf{gravity}$

$\textbf{algorithm:} \ solve(x\leftarrow \text{gravity})$

• $x \text{ is the root, let } dep(x) = 0$
• $getDep(x \ \cup \ subTree)$
  $~~~~~~$$\rightarrow \textbf{cal}(x)$
• $\textbf{for} \ \forall (x, y) \in [s_1, s_2, \cdots, s_k], s_i \text{ is subTree}$
  $~~~~~~$$sn = \text{size}(y)$
  $~~~~~~$$root \leftarrow getRoot(y), solve(root)$

$\textbf{algorithm:} \ \textbf{cal}(x)$

• $\text{fwick}.add(dep(x), 1)$

• $\textbf{for} \ \forall e(x, y) \in [S_i]$
  $~~~~~~$$dep(y)=dep(x)+w(x, y)$
  $~~~~~~$$getDep(y \ \cup \ S_i) \xrightarrow{dep} vec[\cdots]$

  $~~~~~~$$\textbf{for} \ \forall(d:vec)$
  $~~~~~~$$\textbf{i)} \ \text{fwick}.ask(K-d) \text{ count how many: }$
  $~~~~~~~~~~$$(S_j | S_j \neq S_i)+(d \in S_i) \leqslant K$
  $~~~~~~$$\textbf{ii)} \ \textbf{then} \ \text{fwick}.add(d \in S_i, 1)$

• $\text{reset fenwick}$
  $\textbf{for} \ \forall (d:vec)$
  $~~~~~~$$\text{fwick}.add(d, -1)$
  $\text{fwick}.add(dep(x), -1)$

const int maxn = 1e5 + 10;
const int MAXN = maxn << 5;
const int inf = 0x3f3f3f3f;
int N, K;

// == Fenwick ==
class Fwick {
public:
    vector<int> C;
    int n;

    void resize(int n) {
        this->n = n;
        C.resize(n);
    }

    void clear() {
        fill(C.begin(), C.end(), 0);
    }

    int ask(int x) {
        x++;
        int ans = 0;
        for(; x > 0; x -= lowbit(x)) ans += C[x];
        return ans;
    }

    void add(int x, int d) {
        x++;
        for(; x <= K + 10; x += lowbit(x)) C[x] += d;
    }

    int find(int l, int r, int val) {
        while (l < r) {
            int mid = (l + r) >> 1;
            if(ask(mid) < val) l = mid + 1;
            else r = mid;
        }
        return l;
    }
} fwick;
// == Fenwick finished ==

// == Graph definition ==
int m = 0;

class Edge {
public:
    int to, weight;
    Edge *next;

    Edge() {}
    Edge(int to, int w) : to(to), weight(w) {
        next = NULL;
    }
} edges[maxn << 1], *head[maxn];

void add(int u, int v, int w) {
    edges[++m] = Edge(v, w);
    edges[m].next = head[u];
    head[u] = &edges[m];
}

void initG() {
    m = 0;
    memset(head, 0, sizeof(head));
}
// == Graph finished ==

int sz[maxn];
int dep[maxn];
int vis[maxn];
int sn = N;
int root = 0;

// == get gravity as root ==
void getRoot(int x, int pa, int &res) {
    sz[x] = 1;
    int maxpart = 0;
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        if(vis[y] || y == pa) continue;

        getRoot(y, x, res);
        sz[x] += sz[y];
        maxpart = max(maxpart, sz[y]);
    }
    maxpart = max(maxpart, sn - sz[x]);
    if(maxpart < res) {
        res = maxpart;
        root = x;
    }
}
// == get root finished ==

// == get dep and calculate ==
void getDep(int x, int pa, vector<int> &vec) {
    vec.push_back(dep[x]);
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;

        if(vis[y] || y == pa) continue;
        dep[y] = dep[x] + w;

        if(dep[y] <= K) getDep(y, x, vec);
    }
}

queue<int> buf;
inline void cal(int x, int &ans) {
    fwick.add(dep[x], 1);

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;
        if(vis[y]) continue;

        dep[y] = dep[x] + w;
        vector<int> vec;
        getDep(y, x, vec);

        _for(i, 0, vec.size()) if(K >= vec[i]) {
            ans += fwick.ask(K - vec[i]);
        }

        _for(i, 0, vec.size()) {
            fwick.add(vec[i], 1);
            buf.push(vec[i]);
        }
    }

    while (buf.size()) {
        fwick.add(buf.front(), -1);
        buf.pop();
    }
    fwick.add(dep[x], -1);
}
// == get dep finsihed ==

// == solve ==
void solve(int x, int &ans) {
    dep[x] = 0;
    vis[x] = 1;
    cal(x, ans);

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;

        if(vis[y]) continue;

        sn = sz[y];
        root = 0;
        int res = inf;
        getRoot(y, -1, res);

        solve(root, ans);
    }
}
// == solve finished ==

void init() {
    Set(sz, 0);
    Set(dep, 0);
    Set(vis, 0);
    sn = N;
    root = 0;

    fwick.resize(MAXN);
    fwick.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &N, &K) == 2 && N) {
        init();
        initG();

        // get data
        _for(i, 1, N) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w);
            add(v, u, w);
        }
        // data finished

        int res = inf;
        getRoot(1, -1, res);

        int ans = 0;
        solve(root, ans);
        printf("%d\n", ans);
    }
}

点分治例子

Acwing264

$\textbf{algorithm}$

• $\textbf{solve}(x, \text{ans})$
  $~~~~~~$$\text{dep}(x) = 0, \text{vis}(x) = 1$
  $~~~~~~$$\textbf{cal}(x, ans)$
  $~~~~~~$$\textbf{for} \ \forall y \in son(x)$
  $~~~~~~~~~~$$root \leftarrow getRoot(), \textbf{solve}(root, ans)$

• $\textbf{cal}(x, y)$, 难点在于$\text{cal}$的计算

用 $\textbf{vec1}[\cdots]$ 维护 $\textbf{D}[\cdots], \text{ and }\textbf{vec2}[\cdots]$ 维护 $\textbf{dep}[\cdots]$

const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int N, K;

// == Graph definition ==
int m = 0;

class Edge {
public:
    int to, weight;
    Edge *next;

    Edge() {}
    Edge(int to, int w) : to(to), weight(w) {
        next = NULL;
    }
} edges[maxn << 1], *head[maxn];

void initG() {
    m = 0;
    memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
    edges[++m] = Edge(v, w);
    edges[m].next = head[u];
    head[u] = &edges[m];
}
// == Graph finished ==

// == get root ==
int root = 0;
int sn = N;
int sz[maxn];
int vis[maxn];

void getRoot(int x, int pa, int &res) {
    sz[x] = 1;

    int maxpart = 0;
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        if(vis[y] || y == pa) continue;

        getRoot(y, x, res);

        sz[x] += sz[y];
        maxpart = max(maxpart, sz[y]);
    }
    maxpart = max(maxpart, sn - sz[x]);

    if(maxpart < res) {
        res = maxpart;
        root = x;
    }
}
// == get root finished ==

// == solve ==
int dep[maxn];
int D[maxn];
int dp[maxn];

void dfs(int x, int pa, vector<int> &vec1, vector<int> &vec2) {
    vec1.push_back(D[x]);
    vec2.push_back(dep[x]);
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;

        if(vis[y] || y == pa) continue;

        dep[y] = dep[x] + 1;
        D[y] = D[x] + w;

        if(D[y] <= 1e6) dfs(y, x, vec1, vec2);
    }
}

queue<int> que;
void cal(int x, int &ans) {
    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;

        if(vis[y]) continue;

        vector<int> vec1, vec2;
        dep[y] = dep[x] + 1;
        D[y] = D[x] + w;
        dfs(y, x, vec1, vec2);

        _for(i, 0, vec1.size()) {
            if(K >= vec1[i]) ans = min(ans, dp[K - vec1[i]] + vec2[i]);
        }

        _for(i, 0, vec1.size()) {
            que.push(vec1[i]);
            dp[vec1[i]] = min(dp[vec1[i]], vec2[i]);
        }
    }
    while (que.size()) {
        dp[que.front()] = inf;
        que.pop();
    }
}

void solve(int x, int &ans) {
    vis[x] = 1;
    dep[x] = 0;
    D[x] = 0;
    dp[0] = 0;

    cal(x, ans);

    for(const Edge *e = head[x]; e; e = e->next) {
        int y = e->to;
        int w = e->weight;

        if(vis[y]) continue;

        sn = sz[y];
        root = 0;
        int res = inf;
        getRoot(y, x, res);

        solve(root, ans);
    }
}
// == solve finished ==

void init() {
    root = 0;
    sn = N;
    Set(sz, 0);
    Set(vis, 0);
    Set(dep, 0);
    Set(D, 0);
    Set(dp, inf);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &K);
    initG();
    init();

    _for(i, 1, N) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u++; v++;
        add(u, v, w);
        add(v, u, w);
    }

    // then solve the problem
    int res = inf;
    getRoot(1, -1, res);
    int ans = inf;
    solve(root, ans);

    if(ans == inf) printf("-1\n");
    else printf("%d\n", ans);
}

一些算法技巧

$\textbf{algorithm} \ \textbf{差分}$

$A[...]=A_1,A_2,A_3, \cdots ,A_n$
$B_i = A_i - A_{i-1}, \ B_1 = A_1$
$B$ 就是 $A$ 的差分序列

• 性质1

$$A_i = \sum_{j = 1}^{i} B_j$$

• 性质2
  $A[l, r] \xleftarrow{+C}$
  给区间 $A[l, r]$ 的元素都加上 $C$
  $\Leftrightarrow B_{r+1} - C, B_{l} + C$

Acwing100

$\textbf{algorithm,} \ \textbf{solve} \ (B_i, B_j) , i < j$
目标是把 $B_2, B_3\cdots, B_n$ 全部变成 $0$

• $2\leqslant i < j \leqslant n, \text{ 能够处理 } B[2\cdots n] \text{ 中的 } 2 \text{ 个数 } B_i, B_j$
  改变的是区间 $A[i, \cdots, j-1]$
  在一正一负的时候尽可能用这种操作

• $i = 1, 2 \leqslant j \leqslant n$
  改变的是 $A[\cdots]$ 的前缀

• $2 \leqslant i \leqslant n, j = n + 1$
  改变的是 $A[\cdots]$ 的后缀

• $i = 1, j = n + 1$
  改变了整个 $A$ 序列，无意义

$\textbf{algorithm}$

• $\textbf{do} \ \text{type i) , when } B_i \cdot B_j <0$
• $\text{other, do type ii) or iii)}$
  $\text{example, remain }\textbf{r} \ \textbf{unpaired}$
  $\rightarrow [\text{ii)}, \text{iii)}] = (0, r), (1, r), \cdots, (r, 0)$
  $\rightarrow tot =r+1$

const int maxn = 1e5 + 10;
int A[maxn], B[maxn];
int n;

void init() {
    Set(B, 0);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    init();

    _rep(i, 1, n) scanf("%d", &A[i]);

    B[1] = 1;
    _rep(i, 2, n) B[i] = A[i] - A[i - 1];

    ll s1 = 0, s2 = 0;
    _rep(i, 2, n) {
        if(B[i] > 0) s1 += B[i];
        else s2 -= B[i];
    }

    ll ans = min(s1, s2) + abs(s1 - s2);
    cout << ans << endl;

    ll ans2 = abs(s1 - s2) + 1;
    cout << ans2 << endl;
}

树状数组维护差分序列

POJ3468

$[l, r] \xleftarrow{+d}$
$B_i = A_i - A_{i - 1}$

$$\begin{gathered} A_i = \sum_{j = 1}^{i} B_j \\ \ \\ S_{\text{prefix}}(x) = \sum_{i = 1}^{x} A_i = \sum_{i = 1}^{x}\sum_{j = 1}^{i} B_j \\ \ \\ = \sum_{i = 1}^{x}(x-i+1)B_i = (x+1)\sum_{i = 1}^{x}B_i - \sum_{i = 1}^{x}i \cdot B_i \end{gathered}$$

$\textbf{algorithm}$

• $\text{fwick[0]} \leftarrow \sum_{i = 1}^{x} B_i, \quad \text{fwick[1]} \leftarrow \sum_{i = 1}^{x} i B_i$
• $\textbf{change:} \ [l, r]$
  $~~~~~~$$\text{fwick[0]}.add(r+1, -d), \quad \text{fwick[0]}.add(l, d)$
  $~~~~~~$$\text{fwick[1]}.add(r+1, -(r+1)d), \quad \text{fwick[1]}.add(l, ld)$
• $\textbf{ask:} \ [l, r]$
  $~~~~~~$$S(r) = (\text{fwick}[0].ask(r)) \times (r+1) - \text{fwick[1]}(r)$
  $~~~~~~$$S(l -1) = (\text{fwick}[0].ask(l - 1)) \times (l) - \text{fwick[1]}(l - 1)$
  $~~~~~~$$\textbf{ans} = S(r) - S(l - 1)$

const int maxn = 100000 + 10;
int n, m;
ll A[maxn];

// == fenwick definition ==
class Fwick {
public:
    vector<ll> C[2];
    int n;

    void resize(int n) {
        this->n = n;
        _for(i, 0, 2) C[i].resize(n + 1);
    }

    void clear() {
        _for(i, 0, 2) fill(C[i].begin(), C[i].end(), 0ll);
    }

    void add(int k, int x, ll d) {
        int i = x;
        for(; i <= n; i += lowbit(i)) C[k][i] += 1ll * d;
    }

    ll ask(int k, int x) {
        ll ans = 0;
        for(int i = x; i; i -= lowbit(i)) ans += C[k][i];
        return ans;
    }

} fwick;
// == fenwick finsihed ==

ll prefix(int x) {
    return fwick.ask(0, x) * (x + 1) - fwick.ask(1, x);
}

void init() {
    fwick.resize(maxn);
    fwick.clear();
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    init();

    _rep(i, 1, n) {
        scanf("%lld", &A[i]);
        fwick.add(0, i, A[i] - A[i - 1]);
        fwick.add(1, i, i * (A[i] - A[i - 1]));
    }

    // then solve
    while (m--) {
        char cmd[2];
        scanf("%s", cmd);
        if(cmd[0] == 'C') {
            int l, r, d;
            scanf("%d%d%d", &l, &r, &d);

            fwick.add(0, r + 1, -1ll * d);
            fwick.add(0, l, 1ll * d);

            fwick.add(1, r + 1, -1ll * d * (r + 1));
            fwick.add(1, l, 1ll * d * l);
        }
        else {
            int l, r;
            scanf("%d%d", &l, &r);

            ll ans = prefix(r) - prefix(l - 1);
            printf("%lld\n", ans);
        }
    }
}

树状数组求逆序对

$\textbf{algorithm:} \ \textbf{A}[\cdots]$
$\textbf{for} \ \forall i \in [1, n]$
$~~~~~~$$\textbf{check} \ [1, 2, \cdots, i] \rightarrow \textbf{fwick}[\cdots]$
$~~~~~~$$\textbf{fwick}.add(A[i], 1)$

$~~~~~~$$\textbf{fwick}.sum(A[i]) \rightarrow (\text{how many} \leqslant A[i]) \in [1, \cdots, i]$

$$\text{ans} = \sum (i - \text{fwick}.sum(A[i]))$$

class Solution {
public:
    int inversePairs(vector<int>& nums) {
        int n = nums.size();
        #define lowbit(x) (x & (-x))
        typedef long long ll;
        int b[n + 1], a[n + 1];
        
        class Fwick {
        public:
            vector<ll> C;
            int n;
            void resize(int n) {
                this->n = n;
                C.resize(n + 1);
            }
            
            void clear() {
                fill(C.begin(), C.end(), 0);
            }
            
            int sum(int x) {
                int ans = 0;
                for(; x > 0; x -= lowbit(x)) ans += C[x];
                return ans;
            }
            
            int add(int x, int d) {
                for(; x <= n; x += lowbit(x)) C[x] += d;
            }
        } fwick;
        

        for(int i = 1; i <= (int)nums.size(); i++) {
            a[i] = b[i] = nums[i - 1];
        }
        
        sort(b + 1, b + 1 + n);
        int tot = unique(b + 1, b + 1 + n) - b - 1;
        for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + tot, a[i]) - b;
        
        fwick.resize(tot + 1);
        fwick.clear();
        
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            fwick.add(a[i], 1);
            ans += i - fwick.sum(a[i]);
        }
        return ans;
    }
};