CF1416D Graph and Queries

https://www.luogu.com.cn/problem/CF1416D

妙妙套路题

首先可以把每条边的权值设为最后删除的时间,如果没被删则权值为 q + 1 q+1 q+1

建立kruskal重构树，这样就能保证同一颗子树里的可以互相到达

然后删边操作就变成了子树询问，删点操作就是单点修改

用线段树维护dfn序即可

code:

#include
#define N 600050
#define M 500050
using namespace std;
int FA[N << 1];
int get(int x) {
    return x == FA[x]? x : (FA[x] = get(FA[x]));
}
vector g[N];
void insert(int u, int v) { //printf("%d --> %dn", u, v);
    g[u].push_back(v);
}
struct EE {
    int x, y, t;
} e[M << 1];
int cmp(EE x, EE y) {
    return x.t > y.t;
}
int tot, n, m, tim[N];
void kruskal() {
    tot = n;
    sort(e + 1, e + 1 + m, cmp);
    for(int i = 0; i <= 2 * n; i ++ ) FA[i] = i;
    for(int i = 1; i <= m; i ++) {
        int x = get(e[i].x), y = get(e[i].y);
        if(x == y) continue;
        tim[++ tot] = e[i].t;
        insert(tot, x);//, insert(x, tot);
        insert(tot, y);//, insert(y, tot);
        FA[x] = FA[y] = tot;
    }
}

int gs, dfn[N], size[N], fa[N][21], py[N];
void dfs(int u) {
    size[u] = 1;
    dfn[u] = ++ gs; py[gs] = u;
    for(int v : g[u]) {
        if(v == fa[u][0]) continue;
        fa[v][0] = u;
        dfs(v); size[u] += size[v];
    }
}

#define ls (rt << 1)
#define rs (rt << 1 | 1)
int ma[N << 3], a[N];
int update(int l, int r) {
    if(a[l] > a[r]) return l;
    else return r;
}
void build(int rt, int l, int r) {
    if(l == r) {
        ma[rt] = py[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    ma[rt] = update(ma[ls], ma[rs]);
}
void clr(int rt, int l, int r, int x) {
    if(l == r) {
        a[py[l]] = 0;
        return ;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) clr(ls, l, mid, x);
    else clr(rs, mid + 1, r, x);
    ma[rt] = update(ma[ls], ma[rs]);
}
int query(int rt, int l, int r, int L, int R) {
    if(L <= l && r <= R) return ma[rt];
    int mid = (l + r) >> 1, ret = 0;
    if(L <= mid) ret = update(ret, query(ls, l, mid, L, R));
    if(R > mid) ret = update(ret, query(rs, mid + 1, r, L, R));
    return ret;
}
int find(int x, int ti) {
    for(int i = 19; i >= 0; i --) if(fa[x][i] && tim[fa[x][i]] >= ti) x = fa[x][i];
    return x;
}
int qq, ans[M];
struct Q {
    int o, x;
} q[M << 1];
int main() {
    scanf("%d%d%d", &n, &m, &qq);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    for(int i = 1; i <= n; i ++) tim[i] = qq + 1;
    for(int i = 1; i <= m; i ++) {
        scanf("%d%d", &e[i].x, &e[i].y);
        e[i].t = qq + 1;
    }
    for(int i = 1; i <= qq; i ++) {
        scanf("%d%d", &q[i].o, &q[i].x);
        if(q[i].o == 2) e[q[i].x].t = i;
    }

    //for(int i = 1; i <= m; i ++) printf("%d %d %dn", e[i].x, e[i].y, e[i].t); printf("n");
    kruskal();
    //for(int i = 1; i <= tot; i ++) printf("%d ", tim[i]); printf("n");
    for(int i = 1; i <= tot; i ++) if(FA[i] == i) dfs(i);

    for(int j = 1; j <= 19; j ++)
        for(int i = 1; i <= tot; i ++) 
            fa[i][j] = fa[fa[i][j - 1]][j - 1]; 

    build(1, 1, tot);
    for(int i = 1; i <= qq; i ++) if(q[i].o == 1) {
        int x = find(q[i].x, i);
     //   printf("* %d %d  %dn", i, q[i].x, x);
        x = query(1, 1, tot, dfn[x], dfn[x] + size[x] - 1);
        ans[i] = a[x];

        if(a[x]) clr(1, 1, tot, dfn[x]);
    }
    for(int i = 1; i <= qq; i ++) if(q[i].o == 1) printf("%dn", ans[i]);
    return 0;
}