题解 P4847 【银河英雄传说V2】

· · 题解

题外话

这题各位dalao都说是裸的LCT，就我一个人想到splay。。。

然后出题人也只想到LCT，而且跑得巨快，于是比赛时时限是1s。。。

又因为我是蒟蒻，自带大常数，竟然比LCT还慢。。。哭死

结果出题人善良地在比赛时卡我常数在赛后把时限调到2s

正题

这题我一眼平衡树，又因为treap不熟，于是写了splay

一开始对于每个元素都建一棵splay。

若合并：

{

设x合并到y后面

朴素做法：

x=getfa(x);y=getfa(y);
if (x==y) return;
while (rs[B]) B=rs[B];
fa[A]=B;rs[B]=A;
splay(A,0);

卡常：加启发式即可

}

断开：

{

splay(x,0);
fa[ls[x]]=0;ls[x]=0;
pushup(x)

}

查询：

{

if (x==y) return a[x];
fx=getfa(x);fy=getfa(y);
if (fx!=fy) return -1;
splay(x,0);splay(y,x);
return rs[x]==y?a[x]+a[y]+sum[ls[y]]:a[x]+a[y]+sum[rs[y]];

}

完。

代码

#include<bits/stdc++.h>
#define sz 201010
using namespace std;
typedef long long ll;
struct FastIO
{
    inline FastIO& operator>>(int& x)
    {
        x=0;char f=0,ch=getchar();
        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
        while(ch<='9'&&ch>='0') x=x*10+ch-48,ch=getchar();
        return x=(f?-x:x),*this;
    }
    inline FastIO& operator>>(ll& x)
    {
        x=0;char f=0,ch=getchar();
        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
        while(ch<='9'&&ch>='0') x=x*10+ch-48,ch=getchar();
        return x=(f?-x:x),*this;
    }
    inline FastIO& operator>>(double& x)
    {
        x=0;char f=0,ch=getchar();
        double d=0.1;
        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
        while(ch<='9'&&ch>='0') x=x*10+ch-48,ch=getchar();
        if(ch=='.')
        {
            ch=getchar();
            while(ch<='9'&&ch>='0') x+=d*(ch^48),d*=0.1,ch=getchar();
        }
        return x=(f?-x:x),*this;
    }
}read;

void file()
{
    #ifndef ONLINE_JUDGE
    freopen("a.txt","r",stdin);
    #endif
}

ll a[sz];

struct hh{int fa,dep,ch[2];ll sum;}tr[sz];

int getfa(int x){while (tr[x].fa) x=tr[x].fa;return x;}
void pushup(int x)
{
    tr[x].sum=tr[tr[x].ch[0]].sum+tr[tr[x].ch[1]].sum+a[x];
    tr[x].dep=max(tr[tr[x].ch[0]].dep,tr[tr[x].ch[1]].dep)+1;
}
bool get(int x){return tr[tr[x].fa].ch[1]==x;}
void rotate(int x)
{
    int y=tr[x].fa,z=tr[y].fa;
    int k=get(x),w=tr[x].ch[!k];
    if (z) tr[z].ch[get(y)]=x;tr[x].ch[!k]=y;tr[y].ch[k]=w;
    if (w) tr[w].fa=y;tr[x].fa=z;tr[y].fa=x;
    pushup(y);pushup(x);
}
void splay(int x,int to)
{
    while (tr[x].fa!=to)
    {
        int y=tr[x].fa;
        if (tr[y].fa!=to) rotate(get(x)==get(y)?y:x);
        rotate(x);
    }
}
void connect(int x,int y) //head[x]->tail[y]
{
    x=getfa(x);y=getfa(y);
    if (x==y) return;
    if (tr[x].dep>tr[y].dep)
    {
        while (tr[x].ch[0]) x=tr[x].ch[0];
        tr[x].ch[0]=y;tr[y].fa=x;
        splay(y,0);
    }
    else
    {
        while (tr[y].ch[1]) y=tr[y].ch[1];
        tr[y].ch[1]=x;tr[x].fa=y;
        splay(x,0);
    }
}
void cut(int x)
{
    splay(x,0);
    tr[tr[x].ch[0]].fa=0;tr[x].ch[0]=0;
    pushup(x);
}
ll query(int x,int y)
{
    if (x==y) return a[x];
    int fx=getfa(x),fy=getfa(y);
    if (fx!=fy) return -1;
    splay(x,0);splay(y,x);
    int ls=tr[y].ch[0],rs=tr[y].ch[1];
    return get(y)?tr[ls].sum+a[x]+a[y]:tr[rs].sum+a[x]+a[y];
}
int main()
{
    file();
    int n,m,i,x,y;
    read>>n>>m;
    for (i=1;i<=n;i++) read>>a[i];
    for (i=1;i<=n;i++) pushup(i);
    while (m--)
    {
        char ch;cin>>ch;
        if (ch=='M') read>>x>>y,connect(x,y);
        else if (ch=='D') read>>x,cut(x);
        else read>>x>>y,printf("%lld\n",query(x,y));
    }
}

吐槽

出题人太恶心啦！！这份代码最慢的点跑了1200ms，比赛时时限1000ms！！！我的ＡＣ没啦！！！