「大森林」[ZJOI 2016] 大森林

大森林

题目大意：

维护一行树（初始每棵树只有1个点），支持以下操作：

1.区间生长节点长出一个节点

2.区间更换生长节点

3.询问一棵树两点间距离

一道神题，题解都在说 A 话…

什么区间换父亲单点换父亲…

考虑如果在 l" role="presentation"> $l$ 处更换了生长节点，那么就相当于把第 l−1" role="presentation"> $l - 1$ 棵树之后生长的节点都“嫁接”在这个新的生长节点上。我们可以想象对于每一个1操作建一个虚点，然后0操作生长的点都连载这个点上。然后在 l" role="presentation"> $l$ 处 link 过去，在 r+1" role="presentation"> $r + 1$ 处 link 回来。

可以发现询问与时间没有关系。一开始我们把虚点都连成一条“虚链”，我们预处理出时间上离每个 0 操作最近的 1 操作是什么，然后在这个把这个 0 操作新建的点 link 到这个虚点上。然后我们离线扫描线，对于一个 1 操作，我们在 l" role="presentation"> $l$ 处把它的虚点和它的父亲 cut 掉，然后 link 到它对应的实点下面，然后在 r" role="presentation"> $r$ 处 cut 掉它的父亲，link 回链上。

可以发现这么做，在某一个位置，某一个点实际对应的虚点（生长节点）就是它所在“虚链”的顶端。

观察到在 link，cut 的时候类似于对“子树”进行操作。因此不需要有 make_root 这个操作。link 的时候直接 splay 一下就好了。

现在问题是如何统计答案。由于不会存在两个相邻的实点，因此如果我们给实点赋一个点权 1，给虚点赋一个点权 0，那么答案就是两点间权值和了。但是求和我们不能 split，因为这样会破坏树的结构。因此我们选择差分。那么怎么在 LCT 里求 lca？先 access(x)，再 access(y)，access(y)过程中遇到的最后一条虚边的父节点就是 lca 了。

#include<cstdio>
#include<iOStream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
struct node{
    int pos,ind,x,y;
}a[200010];
int tot,q,cnt,fa[300010],son[300010][2],w[300010],real,now,sum[300010],at[300010],ans[300010],gl[300010],gr[300010];
bool cmp(node a,node b)
{
    if(a.pos==b.pos) return a.ind<b.ind;
    return a.pos<b.pos;
}
bool not_root(int x)
{
    if(son[fa[x]][0]==x||son[fa[x]][1]==x) return true;
    return false;
}
void push_up(int x)
{
    sum[x]=w[x];
    if(son[x][0]) sum[x]+=sum[son[x][0]];
    if(son[x][1]) sum[x]+=sum[son[x][1]];
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],kind=x==son[y][0];
    int tmp=not_root(y);
    son[y][!kind]=son[x][kind];
    if(son[x][kind]) fa[son[x][kind]]=y;
    son[x][kind]=y;
    fa[y]=x;
    fa[x]=z;
    if(tmp)
    {
        if(y==son[z][0]) son[z][0]=x;
        else son[z][1]=x;
    }
    push_up(y);
    push_up(x); 
 } 
void splay(int x)
{
    while(not_root(x))
    {
        int y=fa[x],z=fa[y];
        if(not_root(y))
        {
            if((x==son[y][0])^(y==son[z][0])) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    push_up(x);
}
int access(int x)
{
    int y=0;
    for(;x;x=fa[y=x])
        splay(x),son[x][1]=y,push_up(x);
    return y;
}
void Cut(int x)
{
    access(x);
    splay(x);
    son[x][0]=fa[son[x][0]]=0;
    push_up(x);
}
void Link(int x,int y)
{
    splay(x);
    fa[x]=y;
}
inline int read()
{
    char c=getchar();int x=0,flag=1;
    while(!isdigit(c)) flag*=c=='-'?-1:1,c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x*flag;
}
int main()
{
    int n=read(),m=read();
    real=w[1]=sum[1]=at[1]=gl[1]=1,gr[1]=n;
    Link(tot=now=2,1);
    for(int i=1;i<=m;i++)
    {
        int opt=read(),l=read(),r=read(),x;
        if(opt==0)
        {
            Link(at[++real]=++tot,now);
            w[tot]=sum[tot]=1;
            gl[real]=l,gr[real]=r;
        }
        else if(opt==1)
        {
            x=read();
            l=max(l,gl[x]),r=min(r,gr[x]);
            if(l>r) continue;
            Link(++tot,now); //新建虚点 
            a[++cnt]=node{l,i-m,tot,at[x]};
            a[++cnt]=node{r+1,i-m,tot,now};
            now=tot;
        }
        else x=read(),a[++cnt]=node{l,++q,at[r],at[x]};
    }
    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
    {
        if(a[i].ind>0)
        {
            int x=a[i].x,y=a[i].y,z;
            access(x),splay(x),z=sum[x];
            int lca=access(y);splay(y),z+=sum[y];
            access(lca);
            splay(lca);
            ans[a[i].ind]=z-sum[lca]*2;
        }
        else Cut(a[i].x),Link(a[i].x,a[i].y);
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
    return 0;
}

[ZJOI 2016] 大森林

大森林

相关阅读

栏目导航

推荐阅读

热门阅读