洛谷3348 大森林 (LCT + 虚点 + 树上差分)

这可真是道神仙题QWQ问了好多\(dalao\)才稍微明白了一丢丢做法

首先，我们假设不存在\(1\)操作，那么对于询问的一段区间中的所有的树，他们的形态应该是一样的

甚至可以直接理解为\(0\)操作就是表示所有树的生成节点都添加一个儿子

其实就算存在\(1\)操作，也是类似同理的.

这样考虑：

考虑如果在 \(l\)处更换了生长节点，那么就相当于把第 \(l−1\) 棵树之后生长的节点都“嫁接”在这个新的生长节点上。我们可以想象对于每一个\(1\)操作建一个虚点，然后0操作生长的点都连载这个点上。然后在 \(l\) 处 link 过去（就是说link到这个操作对应的那个节点（实点）），在 \(r+1\)r 处 link 回来。

相当于对于加的儿子，我们建的是实点

然后对于每一个\(1\)操作呢，我们新建一个虚点，依次挂在一号节点下面，构成一个虚链，我们通过把0操作的节点挂在虚点，然后从虚点连接实点，从而体现改变生长节点这个操作。

那么QWQ对于一段区间，我们该什么时候link，什么时候cut呢。

这时候！离线！！

因为要求距离，那么我们不妨把实点的点权弄成，然后虚点是0（因为虚点并没有实际意义）

可以发现询问与时间没有关系。一开始我们把虚点都连成一条“虚链”，我们预处理出时间上离每个 0 操作最近的 1 操作是什么，然后在这个把这个 0 操作新建的点 link 到这个虚点上。

（之所以可以这么\(link\)的原因是，虚点的点权都是0，不论当前是对应的哪个生长节点，都不会产生影响，就算是1，虚链的总权值也是1，所以直接上去也没错)

这样，剩下的操作就是\(1\)和\(2\)了

很显然，对于每一棵树，他们之间都是独立的，那我们就可以把剩下的操作按照询问端点排序

（其中，对于一个 1 操作，我们在 \(l\) 处把它的虚点和它的父亲 \(cut\) 掉，然后 \(link\) 到它对应的实点下面，然后在 \(r+1\) 处 \(cut\) 掉它的父亲，\(link\) 回链上）

然后依次去做，不过需要注意的是，对于一个端点来说，你需要把所有该点的修改都弄好，再去回答查询操作）

对于查询操作的话

这里没有必要\(makeroot\)的原因是1.有根树2.最好是为了保持相对的父子关系不变

其实\(makeroot也\)可以，因为不存在子树信息的查询

但是我写的版本就是没有\(makeroot\)的

可以直接\(access(x),splay(x)\)，那么\(sum[x]\)就表示\(1~x\)的路径长度，我们可以用类似查分的方式来求，也就是\(sum[x]+sum[y]-2*sum[lca(x,y)]\) 这里\(sum\)表示路径长度

那\(lct\)怎么求\(lca\)呢?

可以发现，我们第一次\(access(x)\)，从根到x的路径都是实链了，那么我们再一次\(access(y)\)的时候，最后一次轻重链切换的那个节点，就是\(lca\)。

可以理解为两条路径的最深的交点

QWQ那么到这里，这个题基本是解决了

真的是很神仙很神仙QWQ

超级难理解啊

放上我丑陋的代码

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<map>

#include<set>

#define mk makr_pair

using namespace std;

inline int read()

{

  int x=0,f=1;char ch=getchar();

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxn = 3e5+1e2;

int ch[maxn][3];

int fa[maxn],sum[maxn],val[maxn];

int l[maxn],r[maxn]; //表示i这个实点对应的区间是哪些

int ymh[maxn]; //实点的编号

int st[maxn];

int cnt;

int tot;

int xvgen; //最近一次1操作新建的虚点的编号

int n,m;

int son(int x)

{

    if (ch[fa[x]][0]==x) return 0;

    else return 1;

}

bool notroot(int x)

{

    return ch[fa[x]][0]==x || ch[fa[x]][1]==x;

}

void update(int x)

{

    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];

}

void rotate(int x)

{

    int y=fa[x],z=fa[y];

    int b=son(x),c=son(y);

    if (notroot(y)) ch[z][c]=x;

    fa[x]=z;

    ch[y][b]=ch[x][!b];

    fa[ch[x][!b]]=y;

    ch[x][!b]=y;

    fa[y]=x;

    update(y);

    update(x);

}

void splay(int x)

{

    while (notroot(x))

    {

        int oo=0;

        int y=fa[x],z=fa[y];

        int b=son(x),c=son(y);

        if (notroot(y))

        {

         if (b==c) rotate(y);

         else rotate(x);

        }

        rotate(x);

    }

    update(x);

}

int access(int x)

{

    int y=0;

    for (;x;y=x,x=fa[x])

    {

        splay(x);

        ch[x][1]=y;

        update(x);

    }

    return y;

}

void link(int x,int y)

{

    access(x);

    splay(x);

    fa[x]=y;

}

void cut(int x)

{

    access(x);

    splay(x);

    fa[ch[x][0]]=0;

    ch[x][0]=0;

    update(x);

}

struct Node{

    int pos,opt,x,y;

};

Node a[maxn];

bool cmp(Node a,Node b)

{

    if (a.pos==b.pos) return a.opt<b.opt;

    return a.pos<b.pos;

}

int tmp[maxn];

int main()

{

  n=read();m=read();

  l[1]=val[1]=sum[1]=ymh[1]=1;

  r[1]=n;

  tot=2;

  xvgen=2;

  int real=1;

  link(tot,1);

  int oo=0;

  for (int i=1;i<=m;i++)

  {

    int opt=read();

    if(opt==0)

    {

     ymh[++real]=++tot;

     link(tot,xvgen); //每次将当前的新加入的节点，连向最近一次1修改的那个那个虚点

     int ll = read(),rr=read();

     l[real]=ll;

     r[real]=rr;

     val[tot]=sum[tot]=1;

     }

     if (opt==1)

     {

      int ll=read(),rr=read();

      int x=read();

      ll=max(ll,l[x]);

      rr=min(rr,r[x]); //看一眼这个区间是否存在

      if (ll>rr) continue;

      ++tot;

      link(tot,xvgen); //为了构成一个类似毛毛虫的虚链

      a[++cnt]=(Node){ll,-1010,tot,ymh[x]}; //在l处将链断开，然后连到这个虚点对应的实点

        a[++cnt]=(Node){rr+1,-1010,tot,xvgen}; //r+1处把链连回来，重新保持虚链

        xvgen=tot;

     }

     if (opt==2)

     {

      int x=read(),ll=read(),rr=read();

      a[++cnt]=(Node){x,++oo,ymh[ll],ymh[rr]}; //把询问也记录，这里第二位的作用是，保证了断链和复原，一定在询问之前

     }

  }

  sort(a+1,a+1+cnt,cmp);//询问排序

  for (int i=1;i<=cnt;i++)

  {

    int ans=0;

    if(a[i].opt>0)

     {

      access(a[i].x),splay(a[i].x),ans+=sum[a[i].x];

      int l = access(a[i].y);

         splay(a[i].y),ans+=sum[a[i].y];

         access(l),splay(l),ans=ans-2*sum[l];

         //树上求路径长度的通用办法

         //这里splay的原因是，整个splay的信息是在根上，如果不进行splay，你是不知道根是谁的

         tmp[a[i].opt]=ans;

     }

     else

     {

      cut(a[i].x);

      link(a[i].x,a[i].y); //表示把当前需要连接的虚点和实点连接起来

      }

  }

  for (int i=1;i<=oo;i++) cout<<tmp[i]<<"\n";

  return 0;

}

巴特西

洛谷3348 大森林 (LCT + 虚点 + 树上差分)

最新文章

热门文章