必威体育Betway必威体育官网
当前位置:首页 > IT技术

[ZJOI 2016] 大森林

时间:2019-08-09 19:42:07来源:IT技术作者:seo实验室小编阅读:68次「手机版」
 

大森林

题目大意:

维护一行树(初始每棵树只有1个点),支持以下操作:

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

2.区间更换生长节点

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

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

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

考虑如果在 l" role="presentation">l 处更换了生长节点,那么就相当于把第 l−1" role="presentation">l1 棵树之后生长的节点都“嫁接”在这个新的生长节点上。我们可以想象对于每一个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;
}

相关阅读

2016年淘宝新规出台

2016年淘宝新的排名规则已出,相比以前的排名规则,现今的排名规则更加公平与完善。电商们要想使自己的店铺排名靠前,这些排名的规则就

【Autocad】CAD2016-2019所有版本的安装序列号和密钥

CAD所有版本的安装序列号和密钥如下。 AutoCAD2019安装序列号:666-69696969, 667-98989898, 400-45454545, 066-66666666 AutoCAD

2016天猫双十一晚会浙江卫视现场视频直播 明星阵容不

相信很多的网友和seo实验室小编一样,对2016年天猫双十一购物狂欢节都比较期待,对2016天猫双十一晚会的神秘面纱也比较好奇。今天,小

sketchup2016使用鼠标滚轮不能旋转视角该怎么办?

新手使用Sketchup,逐步熟悉过程中、突然发现鼠标滚轮按下之后不再像以前一样可以旋转视角,鼠标图案变成了带上下三角的圆圈,百度了好

2016黑色星期五促销活动及海淘攻略

seo实验室日报:1.一下科技确认完成5亿美元E轮融资,创下国内移动视频行业的单轮融资金额最高纪录。2.中国保信搭上蚂蚁金服,首先盯上

分享到:

栏目导航

推荐阅读

热门阅读