Loading...

洛谷P3203 [HNOI2010]弹飞绵羊

check评论:0 条 remove_red_eye浏览量:429 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-23

$LCT$裸题

我们将每个点的权值设为$1$,求出一个点几次跳出去就相当于求这个点到点$n+1$上所有点的权值和

如果当前点可以直接弹出去,我们把它和$n+1\ link$

修改就先$cut$,再$link$

由于我只会$STL$,常数巨大,所以离开$O2$我就$GG$

#include <bits/stdc++.h>
using namespace std;
int n,m,key[200010],ch[200010][2],f[200010],rev[200010],sum[200010],go[200010];
void update(int x)
{
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];
}
int get(int x)
{
    return ch[f[x]][1]==x;
}
int isroot(int x)
{
    return ch[f[x]][1]!=x&&ch[f[x]][0]!=x;
}
void pushdown(int x)
{
    if(rev[x])
    {
        swap(ch[x][0],ch[x][1]);
        rev[ch[x][0]]^=1;
        rev[ch[x][1]]^=1;
        rev[x]=0;
    }
}
void rotate(int x)
{
    int old=f[x],oldf=f[old],which=get(x);
    if(!isroot(old))
    {
        ch[oldf][get(old)]=x;
    }
    ch[old][which]=ch[x][which^1];
    f[ch[old][which]]=old;
    ch[x][which^1]=old;
    f[old]=x;
    f[x]=oldf;
    update(old);
    update(x);
}
void splay(int x)
{
    stack<int> st;
    st.push(x);
    for(int fa=x;!isroot(fa);fa=f[fa])
    {
        st.push(f[fa]);
    }
    while(!st.empty())
    {
        pushdown(st.top());
        st.pop();
    }
    for(int fa=f[x];!isroot(x);rotate(x),fa=f[x])
    {
        if(!isroot(fa))
        {
            rotate(get(fa)==get(x)?fa:x);
        }
    }
    update(x);
}
void access(int x)
{
    for(int y=0;x;x=f[y=x])
    {
        splay(x);
        ch[x][1]=y;
        update(x);
    }
}
void makeroot(int x)
{
    access(x);
    splay(x);
    rev[x]^=1;
}
void link(int x,int y)
{
    makeroot(x);
    f[x]=y;
}
void cut(int x,int y)
{
    makeroot(x);
    access(y);
    splay(y);
    ch[y][0]=f[x]=0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        key[i]=sum[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&go[i]);
        link(i,((i+go[i])>n?n+1:(i+go[i])));
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int opt,x,y;
        scanf("%d%d",&opt,&x);
        x++;
        if(opt==1)
        {
            makeroot(x);
            access(n+1);
            splay(n+1);
            printf("%d\n",sum[n+1]);
        }
        else
        {
            scanf("%d",&y);
            cut(x,((x+go[x])>n?n+1:(x+go[x])));
            go[x]=y;
            link(x,((x+go[x])>n?n+1:(x+go[x])));
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名