CF1416D 做题心得

上次在某trick中提到了这个题，一开始觉得太毒瘤没有写，现在把它补上了。

感觉实现这个东西，比单纯收获一个trick，收获的东西多太多了。

主要思路

它的主要trick是“反向反向操作日神仙”，也就是，先删掉所有边，反过来做一遍，然后再用撤销的方式正过来再做一遍。

思路的框架就是，先把边都删掉，然后做一个Kruskal重构树。Kruskal重构树有一个性质就是，每一个子树都和某时刻的某联通块对应。

而我们在删边的过程中，每一个点对应的联通块就相当于，先把所有边都删掉，然后把它后面的删边操作都加上去后，它所在的联通块。那这样每个点管一个后缀，容易想到反过来撤销删边操作（即加边）。在这个过程中我们可以知道每个点对应的联通块的根节点 \(anc\)（换句话说，Kruskal重构树最终形态上以 \(anc\) 为根的子树就是这个点当时的联通块）。

然后就相当于每次从一个子树中选最大值，并将其修改为0。在dfs序上线段树做，trival。

细节

注意我们每次要找到联通块的根节点，但是我们还不好轻易的改树形态（路径压缩），Kruskal重构树也没有按秩合并一说。那怎么优化呢？

开两个数组，一个路径压缩，一个不路径压缩，存真实的树。压缩的那个保证复杂度，不压缩的那个保证正确性。俩分开使用。

代码

#include <bits/stdc++.h>

using namespace std;

namespace Flandre_Scarlet

{

    #define N 500005

    #define F(i,l,r) for(int i=l;i<=r;++i)

    #define D(i,r,l) for(int i=r;i>=l;--i)

    #define Fs(i,l,r,c) for(int i=l;i<=r;c)

    #define Ds(i,r,l,c) for(int i=r;i>=l;c)

    #define MEM(x,a) memset(x,a,sizeof(x))

    #define FK(x) MEM(x,0)

    #define Tra(i,u) for(int i=G.st(u),v=G.to(i);~i;i=G.nx(i),v=G.to(i))

    #define p_b push_back

    #define sz(a) ((int)a.size())

    #define all(a) a.begin(),a.end()

    #define iter(a,p) (a.begin()+p)

    int I() {char c=getchar(); int x=0; int f=1; while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return ((f==1)?x:-x);}

    template <typename T> void Rd(T& arg){arg=I();}

    template <typename T,typename...Types> void Rd(T& arg,Types&...args){arg=I(); Rd(args...);}

    void RA(int *p,int n) {F(i,1,n) *p=I(),++p;}

    struct edge{int u,v;} e[N];

    struct op{int t,x;} o[N];

    int val[N];

    int n,m,q;

    void Input()

    {

        Rd(n,m,q);

        F(i,1,n) val[i]=I();

        F(i,1,m) e[i]=(edge){I(),I()};

        F(i,1,q) o[i]=(op){I(),I()};

    }

    class Union_Find

    {

    public:

        int fa[N<<1],anc[N<<1];

        // anc用来路径压缩优化时间, fa保留原树的形状, 保证后面求dfs序的正确性

        // 然而这个trick很逊, 即使保持了原树的形状, 仍不能用于可撤销并查集 ———— 因为 anc 的修改太多了

        int tot=0;

        void clear(int n) {F(i,1,n+m) fa[i]=anc[i]=i; tot=n;}

        int  find(int x) {return x==anc[x]?x:anc[x]=find(anc[x]);}

        void merge(int u,int v)

        {

            u=find(u),v=find(v);

            if (u==v) return;

            ++tot; fa[u]=fa[v]=anc[u]=anc[v]=tot;

        }

    }un;

    int anc[N];

    class Graph

    {

    public:

        int head[N];

        struct node{int v,nx;} e[N]; int ecnt;

        void clear() {MEM(head,-1); MEM(e,-1); ecnt=-1;}

        void add(int u,int v)

        {

            e[++ecnt]=(node){v,head[u]}; head[u]=ecnt;

        }

        void add2(int u,int v) {add(u,v); add(v,u);}

        int st(int u) {return head[u];}

        int to(int i) {return e[i].v;}

        int nx(int i) {return e[i].nx;}

    }G;

    bool vis[N];

    int idfn[N],odfn[N],dfq[N],tick=0;

    void DFS(int u) // dfq 存储访问节点的顺序, 里面存节点, 换句话说就是 dfn 的逆变换

    {

        ++tick; dfq[tick]=u; idfn[u]=tick;

        Tra(i,u) DFS(v);

        odfn[u]=tick;

    }

    struct info{int pos,val;};

    info operator+(info a,info b)

    {

        return a.val>b.val?a:b;

    }

    class SegmentTree

    {

    public:

        info s[N<<2];

        #define ls ix<<1

        #define rs ix<<1|1

        #define inx int ix=1,int L=1,int R=n+m

        #define lson ls,L,mid

        #define rson rs,mid+1,R

        void up(int ix) {s[ix]=s[ls]+s[rs];}

        void Build(inx)

        {

            s[ix].val=val[dfq[L]]; s[ix].pos=L;

            if (L==R) return;

            int mid=(L+R)>>1;

            Build(lson); Build(rson); up(ix);

        }

        void Change(int pos,int val,inx)

        {

            if (L==R) {s[ix]=(info){pos,val}; return;}

            int mid=(L+R)>>1;

            if (pos<=mid) Change(pos,val,lson);

            else          Change(pos,val,rson);

            up(ix);

        }

        info Query(int l,int r,inx)

        {

            if (l<=L and R<=r) return s[ix];

            int mid=(L+R)>>1;

            if (r<=mid) return Query(l,r,lson);

            if (l>mid)  return Query(l,r,rson);

            return Query(l,mid,lson)+Query(mid+1,r,rson);

        }

    }T;

    void Soviet()

    {

        // 先删除所有边, 然后反向遍历, 维护Kruskal重构树

        // 途中预处理出每个查询节点的祖先(用当时的并查集做find), 同时把边加回来

        // 然后再利用Kruskal重构树的结构, 正着做一遍

        F(i,1,q) if (o[i].t==2) vis[o[i].x]=1;

        un.clear(n);

        F(i,1,m) if (!vis[i]) un.merge(e[i].u,e[i].v);

        D(i,q,1)

        {

            int t=o[i].t,x=o[i].x;

            if (t==2)

            {

                un.merge(e[x].u,e[x].v);

            }

            else

            {

                anc[i]=un.find(x);

            }

        }

        G.clear();

        F(i,1,un.tot) if (un.fa[i]!=i) G.add(un.fa[i],i);

        F(i,1,un.tot) if (un.find(i)==i) DFS(i);

        T.Build();

        F(i,1,q)

        {

            if (o[i].t==1)

            {

                int f=anc[i];

                info ans=T.Query(idfn[f],odfn[f]);

                printf("%d\n",ans.val);

                T.Change(ans.pos,0);

            }

        }

    }

    void IsMyWife()

    {

        Input();

        Soviet();

    }

}

#undef int //long long

int main()

{

    Flandre_Scarlet::IsMyWife();

    getchar();

    return 0;

}

巴特西

CF1416D 做题心得

CF1416D 做题心得

主要思路

细节

代码

最新文章

热门文章