F. Graph and Queries（删除反向成合并，联想到并查集，无向图求可到达点最大值）

题：https://codeforces.com/contest/1417/problem/F

题意：给定n个点，m条边，每个点都有点权a[ i ]的无向图。

操作一[1,v],找到从当前图v点出发能到达点的最大的a[ i ]输出,并把该点赋值为0；
操作二[2,v]删除第v条边；

分析：

假设这个图是棵树，那么查询操作可用dfs序的线段树利用该树的根节点来查询区间最大值同时单点更新；
但要支持删边操作，这是我们考虑操作离线，实行逆操作，那么删除边就相当于加边，而加边改变附属关系正是并查集的活；
此时的合并操作影响的是图的连通性，我们要让在某一顺序操作下可能被分成的俩个连通块代表不同子树；
我们先把操作中不用被删去的点先合并起来，合并操作我们可以新建一个根节点，作为当前x，y的祖先，因为查询的时候要得做到对x的询问就是对其祖先的询问；
接着进行逆向合并，做到第3步。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define MP make_pair
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
typedef long long ll;
const int mod=1e9+7;
const int M=2e6+6;
const int inf=0x3f3f3f3f;
const ll INF=1e18;
int a[M],pos[M],op[M],b[M],del[M],f[M],ind[M],outd[M],U[M],V[M],tr[M<<2];
vector<int>g[M];
int n,m,q,cnt;
int Find(int x){
    return x==f[x]?x:f[x]=Find(f[x]);
}
void Merge(int x,int y){
    x=Find(x), y=Find(y);
    if(x==y)
        return;
    n++;
    f[n]=n;
    f[x]=n, f[y]=n;
    g[n].pb(x), g[n].pb(y);
}
void dfs(int u){
    ind[u]=++cnt;
    for(auto v:g[u]){
        if(ind[v])
            continue;
        dfs(v);
    }
    outd[u]=cnt;
}
void up(int root){
    tr[root]=max(tr[root<<1],tr[root<<1|1]);
}
void update(int pos,int c,int root,int l,int r){
    if(l==r){
        tr[root]=c;
        return ;
    }
    int midd=(l+r)>>1;
    if(pos<=midd)
        update(pos,c,lson);
    else
        update(pos,c,rson);
    up(root);
}
int query(int L,int R,int root,int l,int r){
    if(L<=l&&r<=R)
        return tr[root];
    int res=0;
    int midd=(l+r)>>1;
    if(L<=midd)
        res=query(L,R,lson);
    if(R>midd)
        res=max(res,query(L,R,rson));
    return res;
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),pos[a[i]]=i,f[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d%d",&U[i],&V[i]);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&op[i],&b[i]);
        if(op[i]==2)
            del[b[i]]=1;
    }


    ///先把没被删除的连起来，固定的连通块
    for(int i=1;i<=m;i++){
        if(!del[i])
            Merge(U[i], V[i]);
    }
    ///查询b[i]相当于查询Find(b[i])
    for(int i=q;i>=1;i--){
        if(op[i]==1)
            b[i] = Find(b[i]);
        else
            Merge(U[b[i]],V[b[i]]);
    }
    for(int i=1;i<=n;i++)
        if(f[i]==i)
            dfs(i);
    for(int i=1;i<=n;i++)
        update(ind[i],a[i],1,1,n);

    for(int i=1;i<=q;i++){
        if(op[i]==1){
            int ans=query(ind[b[i]],outd[b[i]],1,1,n);
            printf("%d
",ans);
            if(ans)
                update(ind[pos[ans]],0,1,1,n);
        }

    }
    return 0;
}

View Code