线段树分治

线段树分治通过将操作离线，并增加 \(O(\log m)\) 的时间复杂度，使得既有插入又有删除的问题转化为只有插入和撤销的子问题。

某些数据结构容易实现插入操作，但是不易或无法实现删除操作。使用线段树分治就可以将删除操作转化为撤销操作，用栈存储数组的变化即可。

使用线段树分治需要满足以下条件：

• 题目中有插入和删除两种操作；
• 数据结构容易实现插入，但不易实现删除；
• 数据结构是非均摊的，因此撤销的时间复杂度有保障。

我们先对每一个元素求出其出现的时间 \([l,r]\)，即该元素在 \(l\) 时刻插入，\(r+1\) 时刻删除。我们在 \(T+1\) 时刻将所有未删除的元素全部删除，保证 \(r\) 有效。

然后将 \([l,r]\) 拍到线段树上，分解为 \(O(m\log m)\) 个区间，将元素的信息添加到对应的区间上。线段树的性质保证这些区间要么包含要么无交。

接着，对线段树进行 dfs，每遍历到一个节点（区间），就将该节点记录的所有元素都插入到数据结构中，然后向子节点递归。如果当前已经是叶子节点，则直接在数据结构上进行查询即可。子节点递归结束后，撤销该节点产生的所有插入操作。

正确性显然：当位于叶节点 \([l,l]\) 时，只有包含 \(l\) 的区间才有贡献。

P5787 二分图 /【模板】线段树分治

题意

有加边和删边两种操作，你需要在每次操作后判定原图是不是二分图。

动态判定二分图可以使用并查集（带权或扩展域）解决。但是并查集只能维护加边的操作，而无法删除其中的某条边。

考虑线段树分治。我们只需要使用启发式合并的并查集，即可实现非均摊 \(O(\log n)\) 合并，用栈维护即可。

模板代码

#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
const int LOGN = 18;

struct Edge {
    int u, v;
};

int n, m, k;

namespace unf {
    int fa[2 * N], sz[2 * N];
    int sta[2 * N * LOGN][2], top;
    void init() {
        for(int i = 1; i <= n * 2; i++) {
            fa[i] = i;
            sz[i] = 1;
        }
    }
    int find(int x) {
        if(fa[x] == x) return x;
        return find(fa[x]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if(sz[x] < sz[y]) swap(x, y);
        sta[++top][0] = x;
        sta[top][1] = y;
        sz[x] += sz[y];
        fa[y] = x;
    }
    void roll_back() {
        int x = sta[top][0];
        int y = sta[top--][1];
        sz[x] -= sz[y];
        fa[y] = y;
    }
}

namespace SegT {
    vector<Edge> tr[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    void modify(int p, int l, int r, int ql, int qr, const Edge& v) {
        if(ql <= l && r <= qr) {
            tr[p].push_back(v);
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) modify(lc(p), l, mid, ql, qr, v);
        if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, v);
    }
    void solve(int p, int l, int r, bool ans) {
        int pre = unf::top;
        if(ans) {
            for(Edge e : tr[p]) {
                if(unf::find(e.u) == unf::find(e.v)) { ans = false; break; }
                unf::merge(e.u, e.v + n);
                unf::merge(e.v, e.u + n);
            }
        }
        if(l == r) {
            cout << (ans ? "Yes\n" : "No\n");
        } else {
            int mid = (l + r) >> 1;
            solve(lc(p), l, mid, ans);
            solve(rc(p), mid + 1, r, ans);
        }
        while(unf::top != pre) unf::roll_back();
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) {
        int u, v, l, r;
        cin >> u >> v >> l >> r;
        if(++l > r) continue;
        SegT::modify(1, 1, k, l, r, (Edge){u, v});
    }

    unf::init();

    SegT::solve(1, 1, k, true);

    return 0;
}

P3733 [HAOI2017] 八纵八横

题意

给定一个无向连通图 \(G=(V,E)\)，边有边权。定义一个环（不要求为简单环）的权值为边权异或和。

有两种操作：

• 向图中加入一条边；
• 删除一条以前加入的边（不会删除初始图中的边）；

要求你在每次操作结束后，输出所有环的权值的最大值。

我们随便选择初始图 \(G\) 的一棵生成树，对于每一条非树边，它都能和树边形成一个环，这样的环称为基本环。能够证明，任意环都可以被表示为一些基本环的异或。

因此，我们只需要使用线性基维护所有基本环，就可以快速查询答案。

然而，普通的线性基无法实现删除操作。又因为没有强制在线，因此考虑线段树分治，将删除操作变为撤销操作。

线性基不是均摊的，因此我们只需要用栈记录数组的变化，即可实现撤销操作。

代码

#include<iostream>
#include<bitset>
#include<vector>
#define w_tp bitset<1005>
using namespace std;
const int N = 510;
const int M = 510;
const int LOGN = 1002;
const int Q = 1010;

char buf[LOGN];
int buf_top;
void print(w_tp x) {
    for(int i = 0; i < 1000; i++) {
        buf[++buf_top] = x[i] + '0';
    }
    while(buf[buf_top] == '0') --buf_top;
    if(!buf_top) ++buf_top;
    while(buf_top) putchar(buf[buf_top--]);
}

struct Edge {
    int u, v;
    w_tp w;
};

struct _Edge {
    int v;
    w_tp w;
    int next;
} pool[2 * M];
int ne = 1, head[N];

void addEdge(int u, int v, const w_tp &w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, m, t;

w_tp pw2[LOGN];
w_tp bs[LOGN];
w_tp c_ans;
int sta[Q * 11], top;
void insert(w_tp x) {
    for(int i = LOGN - 1; i >= 0; i--) {
        if(x[i]) {
            if(bs[i].any()) x ^= bs[i];
            else {
                bs[i] = x;
                sta[++top] = i;
                return;
            }
        }
    }
}

void roll_back() {
    bs[sta[top--]] = 0;
}

w_tp s[N];
int vis[N];
void dfs(int u, int ef) {
    vis[u] = 1;
    for(int i = head[u]; i; i = pool[i].next) {
        if(i == ef) continue;
        int v = pool[i].v;
        const w_tp &w = pool[i].w;
        if(vis[v]) {
            insert(s[u] ^ s[v] ^ w);
        } else {
            s[v] = s[u] ^ w;
            dfs(v, i ^ 1);
        }
    }
}

namespace SegT {
    vector<Edge> tr[4 * Q];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    void modify(int p, int l, int r, int ql, int qr, const Edge& v) {
        if(l > r) return;
        if(ql <= l && r <= qr) {
            tr[p].push_back(v);
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) modify(lc(p), l, mid, ql, qr, v);
        if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, v);
    }
    void solve(int p, int l, int r) {
        if(l > r) return;
        int pre = top;
        for(Edge &e : tr[p]) {
            insert(s[e.u] ^ s[e.v] ^ e.w);
        }
        if(l == r) {
            c_ans = 0;
            for(int i = LOGN - 1; i >= 0; i--) {
                if(!c_ans[i] && bs[i][i]) c_ans ^= bs[i];
            }

            print(c_ans);
            cout << '\n';
        } else {
            int mid = (l + r) >> 1;
            solve(lc(p), l, mid);
            solve(rc(p), mid + 1, r);
        }
        while(top > pre) roll_back();
    }
}

Edge edg[Q];
int app[Q], naq;

int main() {

    cin >> n >> m >> t;
    for(int i = 1; i <= m; i++) {
        int u, v;
        w_tp w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    dfs(1, 0);

    c_ans = 0;
    for(int i = LOGN - 1; i >= 0; i--) {
        if(!c_ans[i] && bs[i].any()) c_ans ^= bs[i];
    }

    print(c_ans);
    cout << '\n';

    for(int i = 1; i <= t; i++) {
        string op;
        cin >> op;
        if(op == "Add") {
            app[++naq] = i;
            cin >> edg[naq].u >> edg[naq].v >> edg[naq].w;
        } else if(op == "Cancel") {
            int id;
            cin >> id;
            SegT::modify(1, 1, t, app[id], i - 1, edg[id]);
            app[id] = -1;
        } else {
            int id;
            cin >> id;
            SegT::modify(1, 1, t, app[id], i - 1, edg[id]);
            app[id] = i;
            cin >> edg[id].w;
        }
    }

    for(int i = 1; i <= naq; i++) {
        if(~app[i]) SegT::modify(1, 1, t, app[i], t, edg[i]);
    }

    SegT::solve(1, 1, t);

    return 0;
}

P9168 [省选联考 2023] 人员调度

题意

有一棵 \(n\) 个节点的有根树，根节点是 \(1\) 号节点。每个节点对应一个可重集 \(S_i\)。你可以进行若干次操作，每次操作你可以选定一个节点 \(u\) 和 \(S_u\) 中的一个元素 \(x\)，然后选定一个 \(u\) 子树内的节点 \(v\)，将 \(x\) 从 \(S_u\) 移动到 \(S_v\) 中。最终，你会获得 \(\sum_{u}\max\{S_u\}\) 的价值。

初始时所有可重集为空，你需要维护两种操作，并在每次操作之后输出能够得到的最大价值：

• 向 \(S_u\) 加入一个元素 \(x\)；
• 从 \(S_u\) 中删除一个 \(x\)，保证 \(x\in S_u\)；

\(n,m\le 10^5\)

静态问题和简化模型

考虑静态问题怎么做。假设 \(u\) 的所有儿子子树的内部已经分配完成，考虑挂在 \(u\) 节点上的员工：如果儿子子树内存在空位，那么 \(u\) 会优先填充这些空位；没有空位之后，\(u\) 会选择子树中最劣的一个位置踢掉，然后自己加进去。

考虑如何进一步刻画这个过程。我们可以将子树内产生贡献的员工从大到小排成一个序列，如果子树内有空位，那么序列的长度小于子树大小之和；否则取等。对于 \(u\) 节点，依照上面的过程我们会先尝试用 \(u\) 节点本身的员工将序列长度补充到 \(sz[u]\)；然后，我们会剔除序列末尾更劣的一个后缀，并加入 \(u\) 的部分员工。

这个过程可以看作是将各个子树的序列依次拼接，然后再把 \(u\) 的员工也加入序列，最后从小到大排序，保留前 \(sz[u]\) 个元素。

动态维护

先考虑只有插入操作怎么做。我们关心新加的员工是否会产生贡献，并且是否会替换其他的员工。注意到，在序列中被删除的员工，以后也不可能产生贡献，因此自动将他们删除，不会改变答案。

如果插入时，\(u\) 的根链的序列都没有溢出，那么 \(u\) 将会直接插入。否则，在第一个溢出的位置 \(t\)，\(u\) 要么替换掉最劣的一个人，自己保留到根，要么直接被干掉，不产生贡献。而那些原本就已经被淘汰的员工，如果他们有实力淘汰 \(u\)，那么 \(u\) 也一定不能在 \(t\) 处存活下来；而且上面也分析过，直接删除它们不会影响答案。

我们需要动态查询根链上第一个满的位置，并且支持链加；还要查询子树内的最小值。使用树剖和线段树维护即可。

带删除

对于删除操作，发现操作都是非均摊的，线段树分治即可。

时间复杂度 \(O(q\log^2 n\log q)\)。

代码

#include<iostream>
#include<vector>
#include<set>
#define ll long long
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int LOGN = 19;
const int INF = 0x3f3f3f3f3f3f3f3f;

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, k, m, nq, nk;

int dep[N], sz[N], fa[N], son[N];
int top[N], dfn[N], id[N], dt;

void dfs1(int u, int a0) {
    dep[u] = dep[a0] + 1;
    sz[u] = 1;
    fa[u] = a0;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp) {
    dfn[u] = ++dt;
    id[dt] = u;
    top[u] = tp;
    if(!son[u]) return;
    dfs2(son[u], tp);
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == son[u]) continue;
        dfs2(v, v);
    }
}

namespace SegT1 {

    struct Node {
        int val, dep, id;
        inline const Node& operator+(const Node &b) const {
            if(val != b.val) return val < b.val ? *this : b;
            return dep > b.dep ? *this : b;
        }
        inline const Node& operator+=(int x) {
            val += x;
            return *this;
        }
    } tr[4 * N];
    int tag[4 * N];

    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }

    inline void move_tag(int p, int tg) {
        tr[p] += tg;
        tag[p] += tg;
    }
    inline void push_down(int p) {
        if(!tag[p]) return;
        move_tag(lc(p), tag[p]);
        move_tag(rc(p), tag[p]);
        tag[p] = 0;
    }
    inline void push_up(int p) {
        tr[p] = tr[lc(p)] + tr[rc(p)];
    }
    void build(int p, int l, int r) {
        if(l == r) {
            tr[p] = {sz[id[l]], dep[id[l]], id[l]};
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) {
            move_tag(p, v);
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    Node query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return tr[p];
        push_down(p);
        int mid = (l + r) >> 1;
        if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
        if(qr <= mid) return query(lc(p), l, mid, ql, qr);
        return query(lc(p), l, mid, ql, qr) + query(rc(p), mid + 1, r, ql, qr);
    }

}

multiset<int> f[N];
int fm[N];

namespace SegT2 {
    int mn[4 * N];
    using SegT1::lc;
    using SegT1::rc;
    void push_up(int p) {
        int l = lc(p), r = rc(p);
        if(fm[mn[l]] < fm[mn[r]]) mn[p] = mn[l];
        else mn[p] = mn[r];
    }
    void build(int p, int l, int r) {
        if(l == r) {
            mn[p] = id[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void update(int p, int l, int r, int q) {
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(q <= mid) update(lc(p), l, mid, q);
        else update(rc(p), mid + 1, r, q);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return mn[p];
        int mid = (l + r) >> 1;
        if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
        if(qr <= mid) return query(lc(p), l, mid, ql, qr);
        int rl = query(lc(p), l, mid, ql, qr), rr = query(rc(p), mid + 1, r, ql, qr);
        return fm[rl] < fm[rr] ? rl : rr;
    }
}

struct Node {
    int p, v;
};

// 路径加
void add_path(int p, int v) {
    while(p) {
        SegT1::add(1, 1, n, dfn[top[p]], dfn[p], v);
        p = fa[top[p]];
    }
}

// 查询第一个满的祖先
int query_path(int p) {
    while(p) {
        SegT1::Node res = SegT1::query(1, 1, n, dfn[top[p]], dfn[p]);
        if(res.val == 0) return res.id;
        p = fa[top[p]];
    }
    return 0;
}

struct Op {
    int op;
    Node v;
} sta[4 * N];
int tp;

ll ans;

// 将一个人插入最优解
void insert_people(int p, int v) {
    ans += v;
    f[p].insert(v);
    fm[p] = *f[p].begin();
    add_path(p, -1);
    SegT2::update(1, 1, n, dfn[p]);
}

// 表示将这个人从最优解中删去，被另一个人取代了
void del_people(int p, int v) {
    ans -= v;
    f[p].erase(f[p].find(v));
    fm[p] = *f[p].begin();
    add_path(p, 1);
    SegT2::update(1, 1, n, dfn[p]);
}

// 新加入一个员工
void add_people(Node x) {
    int y = query_path(x.p);
    if(!y) {
        sta[++tp] = {1, x.p, x.v};
        insert_people(x.p, x.v);
    } else {
        int z = SegT2::query(1, 1, n, dfn[y], dfn[y] + sz[y] - 1);
        if(fm[z] >= x.v) return;
        sta[++tp] = {-1, z, fm[z]};
        del_people(z, fm[z]);
        sta[++tp] = {1, x.p, x.v};
        insert_people(x.p, x.v);
    }
}

void roll_back() {
    if(sta[tp].op == 1) del_people(sta[tp].v.p, sta[tp].v.v);
    else insert_people(sta[tp].v.p, sta[tp].v.v);
    --tp;
}

namespace SegT_pt {
    vector<Node> tr[4 * N];
    using SegT1::lc;
    using SegT1::rc;
    void modify(int p, int l, int r, int ql, int qr, const Node& v) {
        if(ql <= l && r <= qr) {
            tr[p].push_back(v);
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) modify(lc(p), l, mid, ql, qr, v);
        if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, v);
    }
    void work(int p, int l, int r) {
        int pre = tp;
        for(Node &i : tr[p]) add_people(i);
        if(l == r) {
            cout << ans << ' ';
        } else {
            int mid = (l + r) >> 1;
            work(lc(p), l, mid);
            work(rc(p), mid + 1, r);
        }
        while(tp > pre) roll_back();
    }
}

Node a[2 * N];
int app[2 * N];
void add(int tm, int id, int p, int v) {
    app[id] = tm;
    a[id] = {p, v};
}
void del(int tm, int id) {
    if(!app[id]) return;
    SegT_pt::modify(1, 1, nq, app[id], tm - 1, a[id]);
    app[id] = 0;
}

signed main() {

    cin >> n >> n >> k >> m;
    nk = k;
    nq = m + 1;
    for(int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        addEdge(x, i);
    }
    for(int i = 1; i <= k; i++) {
        int p, v;
        cin >> p >> v;
        add(1, i, p, v);
    }
    for(int i = 1; i <= m; i++) {
        int op, p, v, id;
        cin >> op;
        if(op == 1) {
            cin >> p >> v;
            add(i + 1, ++nk, p, v);
        } else {
            cin >> id;
            del(i + 1, id);
        }
    }

    for(int i = 1; i <= nk; i++) del(nq + 1, i);

    dfs1(1, 0);
    dfs2(1, 1);

    for(int i = 1; i <= n; i++) f[i].insert(INF);
    for(int i = 1; i <= n; i++) fm[i] = INF;

    SegT1::build(1, 1, n);
    SegT2::build(1, 1, n);

    SegT_pt::work(1, 1, nq);

    cout << endl;

    return 0;
}