题解 CF1416D 【Graph and Queries】

duyi · 2020-09-28 22:41:39 · 题解

来我的博客看看吧

CF1416D Graph and Queries

题目大意

题目链接

给你一张 n 个点 m 条边的无向图。点有点权，每个点的点权 p_i 是 1 到 n 的正整数且互不相同。

依次进行 q 次操作，每次操作是如下两种之一：

特别地，当所有 v 能到达的点点权都为 0 时，u 是未定义的。但此时选任意一个节点作为 u 答案都是 0，所以你只需要输出 0 即可。

数据范围：1\leq n\leq 2\cdot10^5，1\leq m\leq 3\cdot 10^5，1\leq q\leq 5\cdot10^5。

本题题解

不会删边。所以考虑离线，按时间倒序进行操作，删边变成加边。

但是遇到的麻烦是，操作 1 是正序进行的，如果我们倒序操作，就不知道当前哪些点 p_u = 0 了。

解决方法是，先倒序遍历一遍所有操作，按“加边”的顺序，建出重构树。重构树优美的性质是，对任意一个节点 v，在某个时刻之前和它连通的节点，恰好是重构树上 v 的某个祖先的子树。并且我们可以通过树上倍增，在 O(\log n) 的时间内找到这个祖先。

建出重构树后，我们回到正向的时间线。按正序处理所有询问（操作 1）。前面说过，在某个时刻和 v 连通的节点，是 v 某个祖先的子树。先倍增找到这个祖先。它的子树是 dfs 序上连续的一段。我们预处理出重构树的 dfs 序，那么问题转化为求区间最大值，支持单点修改。可以用线段树维护。

时间复杂度 O((n+m+q)\log n)。

总结

因为 LCT 是垃圾，所以我们不考虑它。那么对于删边操作，其实我们能使用的手段是很有限的。

例如，一个经典的思路是把询问分块。只维护进入本块之前的连通性，对本块内的贡献暴力计算。不过我顺着此思路思考本题并没有得到很好的结果。

另一个思路就是倒序、删边变加边了。但是本题的特殊之处在于，它的另一种操作（操作 1）强烈依赖正序的时间线。所以我们不是简单的倒序操作，而是先倒序预处理出一个数据结构，然后用这个数据结构来正序地操作和回答询问。

顺便扯一句，这道题让我想到了最近热映的一部电影：《信条》，讲的就是一条正序时间线、一条倒序时间线，交织在一起，发生的事情。而本题里的“重构树”这个工具，就好像是《信条》里未来人传送给现代人的“逆向武器”和“算法”。

参考代码

实际提交时，建议加上读入优化，详见本博客公告。

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

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 2e5, MAXM = 3e5, MAXQ = 5e5;
const int LOG = 18;

int n, m, q, val[MAXN + 5];
bool init_in_map[MAXM + 5];
struct Edge_t {
    int u, v;
};
struct Query_t {
    int op, x;
};

Edge_t edges[MAXM + 5], edges_sorted[MAXM + 5];
Query_t queries[MAXQ + 5];
int cnt_e, tim[MAXQ + 5];

int fa[MAXN * 2 + 5], cnt_node;
inline int get_fa(int u) { return (u == fa[u]) ? u : (fa[u] = get_fa(fa[u])); }
inline int new_node() {
    ++cnt_node;
    fa[cnt_node] = cnt_node;
    return cnt_node;
}

struct EDGE { int nxt, to; } edge[MAXN * 2 + 5];
int head[MAXN * 2 + 5], tot;
inline void add_edge(int u, int v) { edge[++tot].nxt = head[u]; edge[tot].to = v; head[u] = tot; }

int node_tim[MAXN * 2 + 5]; // 树上这个节点代表的加边时间
int dfn[MAXN + 5], rev[MAXN + 5], min_dfn[MAXN * 2 + 5], max_dfn[MAXN * 2 + 5], cnt_dfn;
int anc[MAXN * 2 + 5][LOG + 1];

void dfs(int u) {
    for(int i = 1; i <= LOG; ++i) {
        anc[u][i] = anc[anc[u][i - 1]][i - 1];
    }
    bool is_leaf = 1;
    min_dfn[u] = n * 2;
    for(int i = head[u]; i; i = edge[i].nxt) {
        int v = edge[i].to;
        is_leaf = 0;
        anc[v][0] = u;
        dfs(v);
        ckmin(min_dfn[u], min_dfn[v]);
        ckmax(max_dfn[u], max_dfn[v]);
    }
    if(is_leaf) {
        ++cnt_dfn;
        min_dfn[u] = max_dfn[u] = dfn[u] = cnt_dfn;
        rev[cnt_dfn] = u;
    }
}
int get_anc(int u, int t) {
    // u 的最高的 node_tim <= t 的祖先
    int v = u;
    for(int i = LOG; i >= 0; --i) {
        if(anc[v][i] && node_tim[anc[v][i]] <= t) {
            v = anc[v][i];
        }
    }
    return v;
}

struct SegmentTree {
    int mx[MAXN * 4 + 5], mx_pos[MAXN * 4 + 5];
    void push_up(int p) {
        if(mx[p << 1] > mx[p << 1 | 1]) {
            mx[p] = mx[p << 1];
            mx_pos[p] = mx_pos[p << 1];
        } else {
            mx[p] = mx[p << 1 | 1];
            mx_pos[p] = mx_pos[p << 1 | 1];
        }
    }
    void build(int p, int l, int r) {
        if(l == r) {
            mx[p] = val[rev[l]];
            mx_pos[p] = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        push_up(p);
    }
    void point_modify(int p, int l, int r, int pos) {
        if(l == r) {
            mx[p] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) {
            point_modify(p << 1, l, mid, pos);
        } else {
            point_modify(p << 1 | 1, mid + 1, r, pos);
        }
        push_up(p);
    }
    pii query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && qr >= r) {
            return make_pair(mx[p], mx_pos[p]);
        }
        int mid = (l + r) >> 1;
        pii res = mk(0, 0);
        if(ql <= mid) {
            res = query(p << 1, l, mid, ql, qr);
        }
        if(qr > mid) {
            ckmax(res, query(p << 1 | 1, mid + 1, r, ql, qr));
        }
        return res;
    }
    SegmentTree() {}
}SegT;

int main() {
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> val[i];
    }
    for(int i = 1; i <= m; ++i) {
        cin >> edges[i].u >> edges[i].v;
        init_in_map[i] = 1;
    }
    for(int i = 1; i <= q; ++i) {
        cin >> queries[i].op >> queries[i].x;
        if(queries[i].op == 2) {
            assert(init_in_map[queries[i].x] == 1);
            init_in_map[queries[i].x] = 0;
        }
    }
    for(int i = 1; i <= m; ++i) {
        if(init_in_map[i]) {
            ++cnt_e;
            edges_sorted[cnt_e] = edges[i];
        }
    }
    for(int i = q; i >= 1; --i) {
        if(queries[i].op == 2) {
            ++cnt_e;
            edges_sorted[cnt_e] = edges[queries[i].x];
        } else {
            tim[i] = cnt_e;
        }
    }

    assert(cnt_e == m);
    for(int i = 1; i <= n; ++i) {
        new_node();
    }
    for(int i = 1; i <= m; ++i) {
        int u = get_fa(edges_sorted[i].u);
        int v = get_fa(edges_sorted[i].v);
        if(u != v) {
            int par = new_node();
            fa[u] = fa[v] = par;
            node_tim[par] = i;
            add_edge(par, u);
            add_edge(par, v);
        }
    }
    for(int i = 1; i <= cnt_node; ++i) {
        if(get_fa(i) == i) {
            dfs(i);
        }
    }
    assert(cnt_dfn == n);
    SegT.build(1, 1, n);
    for(int i = 1; i <= q; ++i) {
        if(queries[i].op == 1) {
            int u = queries[i].x;
            int v = get_anc(u, tim[i]);

            pii qres = SegT.query(1, 1, n, min_dfn[v], max_dfn[v]);
            cout << qres.fi << endl;
            if(qres.fi) {
                SegT.point_modify(1, 1, n, qres.se);
            }
        }
    }
    return 0;
}