线段树分治常常用来解决以下问题：

修改只在某一个时间区间上成立，但是维护的数据不支持随机删除，只能支持撤销最新操作。

这个时候，以时间顺序模拟就会失效。此时，我们在时间轴上建一棵线段树，就可以把每个操作的事件区间放到线段树的节点上。

接下来对这棵线段树进行 dfs，就可以在 dfs 的路上顺便执行修改与撤销。在叶节点统计答案即可。

设询问区间个数为 $q$，时间轴长度与 $q$ 同级（否则可以离散化），单次操作/撤销复杂度为 $T$，则把区间放到树上的时间复杂度为 $O(q \log q)$，dfs 的时间复杂度为 $O(Tq)$。

P4588 [TJOI2018] 数学计算

题意

维护一个数 $x$，初始为 $1$，两种操作：

1. $x \gets x \times m \mod M$
2. 移除第 $p$ 个操作，保证必为操作 1，且每个操作至多移除一次

（不模 $M$ 的值极大，不可维护，且 $M$ 为合数）

发现由于 $M$ 为合数，不能做除法，也就不能实现随机删除。

所幸我们可以用一个栈记录历史值，实现撤销最新操作。因此可以用线段树分治。

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

typedef long long ll;
const int maxq=1e5+100;
int M, m[maxq];
int ans[maxq];

struct segt {
    vector<int> op[maxq * 4];
    stack<int> X;
    
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return (x<<1)|1; }
    inline int md(int x, int y) { return (x+y)>>1; }
    
    void add_op(int tn, int tl, int tr,
                int x, int y, int opi) {
        if (tl > y || tr < x) {
            return;
        }
        
        if (x <= tl && tr <= y) {
            op[tn].push_back(opi);
            return;
        }
        
        int mid = md(tl, tr);
        add_op(lc(tn), tl, mid, x, y, opi);
        add_op(rc(tn), mid+1, tr, x, y, opi);
    }
    
    void dfs(int tn, int tl, int tr) {
        for (int opi: op[tn]) {
            X.push(((ll)X.top()) * m[opi] % M);  // 不开__见祖宗
        }
        
        if (tl == tr) {
            ans[tl] = X.top();
        } else {
            int mid = md(tl, tr);
            dfs(lc(tn), tl, mid);
            dfs(rc(tn), mid+1, tr);
        }
        
        for (int _: op[tn]) {
            // 按道理是要反转的，但是 pop 不用参数，调用次数对就行
            X.pop();
        }
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        segt segtree;  // 这就是我的多测路线！
        segtree.X.push(1);
        
        int q;
        cin >> q >> M;
        
        set<int> alive;
        for (int i=1; i<=q; i++) {
            int op;
            cin >> op;
            
            if (op == 1) {
                cin >> m[i];
                alive.insert(i);
            } else {
                int pos;
                cin >> pos;
                segtree.add_op(1, 1, q, pos, i-1, pos);
                alive.erase(pos);
            }
        }
        
        for (int pos: alive) {
            segtree.add_op(1, 1, q, pos, q, pos);
        }
        
        segtree.dfs(1, 1, q);
        
        for (int i=1; i<=q; i++) {
            cout << ans[i] << '\n';
        }
    }
    
    return 0;
}

P5227 [AHOI2013] 连通图

题意

给定一张图，$k$ 次询问，每次询问给出 $c\le4$ 条边，问如果删除这些边，图是否仍然连通。

判断连通可以使用并查集，但是发现不能删边，只能加边。

正难则反，一条边在某些时刻被删除，相当于它会在若干个时间区间内存在。

于是维护一个可撤销并查集，在这些时间区间上做一次线段树分治即可。

由于拆出来的区间不会超过 $(m+ck)$ 个，时间复杂度 $O\bigl( (m+ck) \log k + k \log n \bigr)$。

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

const int maxn=1e5+100, maxm=2e5+100;
int n, m, k;
int u[maxm], v[maxm];
bool ans[maxn];

struct history {
    int x, y;
};

struct undo_dsu {
    int siz[maxn], fa[maxn];
    history s[maxm];
    int st;
    int part;
    
    void init(int n) {
        st = 0;
        part = n;
        for (int i=1; i<=n; i++) {
            siz[i] = 1;
            fa[i] = i;
        }
    }
    
    inline int find(int x) {
        while (x != fa[x]) {
            x = fa[x];
        }
        return x;
    }
    
    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) {
            s[++st] = {0, 0};
            return;
        }
        
        if (siz[fx] < siz[fy]) {
            swap(fx, fy);
        }
        
        siz[fx] += siz[fy];
        fa[fy] = fx;
        part--;
        
        s[++st] = {fx, fy};
    }
    
    void undo() {
        if (s[st].x == 0) {
            st--;
            return;
        }
        
        int fx=s[st].x, fy=s[st].y;
        st--;
        
        fa[fy] = fy;
        siz[fx] -= siz[fy];
        part++;
    }
} dsu;

struct segt {
    vector<int> record[maxn*4];
    
    inline int lc(int x) { return x<<1; }
    inline int rc(int x) { return (x<<1)|1; }
    inline int md(int x, int y) { return (x+y)>>1; }
    
    void add(int tn, int tl, int tr, int x, int y, int ei) {
        if (tl > y || tr < x) {
            return;
        }
        
        if (x <= tl && tr <= y) {
            record[tn].push_back(ei);
            return;
        }
        
        int mid = md(tl, tr);
        add(lc(tn), tl, mid, x, y, ei);
        add(rc(tn), mid+1, tr, x, y, ei);
    }
    
    void dfs(int tn, int tl, int tr) {
        for (int ei: record[tn]) {
//          printf("in [%d..%d], merge #%d (%d-%d)\n", tl, tr, ei, u[ei], v[ei]);
//          printf("\tnow #parts: %d\n", dsu.part);
            dsu.merge(u[ei], v[ei]);
        }
        
        if (tl == tr) {
            ans[tl] = (dsu.part == 1);
        } else {
            int mid = md(tl, tr);
            dfs(lc(tn), tl, mid);
            dfs(rc(tn), mid+1, tr);
        }
        
        for (int _=0; _<record[tn].size(); _++) {
            dsu.undo();
        }
    }
} segtree;

int last_delete[maxm];  // 0

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        cin >> u[i] >> v[i];
    }
    
    dsu.init(n);
    
    cin >> k;
    for (int t=1; t<=k; t++) {
        int c;
        cin >> c;
        
        while (c--) {
            int ei;
            cin >> ei;
            
            segtree.add(1, 1, k, last_delete[ei]+1, t-1, ei);
            last_delete[ei] = t;
        }
    }
    
    for (int i=1; i<=m; i++) {
        if (last_delete[i] != k) {
            segtree.add(1, 1, k, last_delete[i]+1, k, i);
        }
    }
    
    segtree.dfs(1, 1, k);
    
    for (int i=1; i<=k; i++) {
        cout << (ans[i]? "Connected\n": "Disconnected\n");
    }
    
    return 0;
}

版权所有

版权归属：Phantom-Bird

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

查看此页源代码

贡献者: Phantom-Bird

上一页“查看此页源代码”插件

下一页CF2131